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	2005
Type	Article in Periodical
Magazine / Source	Theoretical Computer Science
MU Faculty or unit	Faculty of Science
Citation
web	http://dx.doi.org/10.1016/j.tcs.2005.09.018
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:	Mathematical structures of algebra and geometry