Regular solutions of language inequalities and well quasi-orders

Warning

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

Authors	KUNC Michal
Year of publication	2004
Type	Article in Proceedings
Conference	Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings
MU Faculty or unit	Faculty of Science
Citation
Web	http://springerlink.metapress.com/link.asp?id=2blp4dvy8m14mmy3
Field	General mathematics
Keywords	Language equation; Regular language; Well quasi-order; Syntactic semigroup; Finite simple semigroup
Description	By means of constructing suitable well quasi-orders of free monoids we prove that all maximal solutions of certain systems of language inequalities are regular. This way we deal with a wide class of systems of inequalities where all constants are languages recognized by finite simple semigroups. In a similar manner we also demonstrate that the largest solution of the inequality XK subset LX is regular provided the language L is regular.
Related projects:	Equational logic of semigroups and applications