Generalized language equations with multiple solutions
type: Item
instance of: scholarly article
title: Generalized language equations with multiple solutions
zbMATH Open document ID: 0606.68071
DOI: 10.1016/0304-3975(86)90115-5
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3980516
zbMATH Keywords: regular language
zbMATH Keywords: L-expressions
author: Ernst L. Leiss
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90115-5
OpenAlex ID: W1970375533
cites work: Derivatives of Regular Expressions
cites work: On equations for regular languages, finite automata, and sequential networks
cites work: On generalized language equations
cites work: Unrestricted complementation in language equations over a one-letter alphabet
cites work: On classes of tractable unrestricted regular expressions
cites work: Q5588675
Recommended article: Maximal and minimal solutions to language equations
Recommended article: Solutions of equations in languages
Recommended article: Implicit language equations: existence and uniqueness of solutions
Recommended article: Decision problems for language equations
Recommended article: Generalized langford languages
Recommended article: Language equations with complementation: decision problems
Recommended article: Q4256623
Recommended article: Language equations
Recommended article: On language equations with invertible operations
Recommended article: Language Equations with Complementation
description: scientific article; zbMATH DE number 3980516