Regular solutions of language inequalities and well quasi-orders

Warning

This publication doesn't include Faculty of Economics and Administration. 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:

You are running an old browser version. We recommend updating your browser to its latest version.