A counterexample to a conjecture concerning concatenation hierarchies

• Authors: KLÍMA Ondřej; ALMEIDA Jorge
• Year of publication: 2009
• Type: Article in Periodical
• Magazine / Source: Information Processing Letters
• MU Faculty or unit: Faculty of Science
• Field: General mathematics
• Keywords: Formal languages; Regular languages; Concatenation hierarchies; Level two; Star-free languages
• Description: We give a counterexample to the conjecture which was originally formulated by Straubing in 1986 concerning a certain algebraic characterization of regular languages of level 2 in the Straubing Thérien concatenation hierarchy of star free languages.

Related projects

• Institute for Theoretical Computer Science
• Mathematical structures and their physical applications
• Algebraic Methods in Automata and Formal Language Theory II