Generalized language equations with multiple solutions (Q1084871)

The class of L-expressions in the variables \(X_ 1,...,X_ m\) over the alphabet A is defined in such a way that every language over A and any of the variables \(X_ 1,...,X_ m\) is an L-expression and if \(\alpha\) and \(\beta\) are L-expressions, then so are the union \(\alpha\cup \beta\), the complement \({\bar \alpha}\) and the concatenation from left \(L\alpha\) with a language L over A. The system of generalized language equations is the system of equations \(X_ i=\alpha_ i\) for \(i=1,...,m\), where \(\alpha_ 1,...,\alpha_ m\) are L-expressions in the variables \(X_ 1,...,X_ m\) over A. The solution of such a system is an m-tuple of languages over A which can be substituted for \(X_ 1,...,X_ m\) to obtain true equalities. The main theorem classifies language equations in one variable according to the number of solutions. Further it is proved that every language equation with at last one solution has a minimal solution contained in every other and a maximal solution containing every other. Certain graphs are introduced for reducing the systems of language equations. Some related topics are shortly mentioned: solving inclusions (analogy to inequalities), equations in which all languages are regular and equations without complementation.