A counterexample to a conjecture concerning concatenation hierarchies

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Science. Official publication website can be found on muni.cz.

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
Citation
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