2003 | OriginalPaper | Buchkapitel
Decision Problems for Language Equations with Boolean Operations
verfasst von : Alexander Okhotin
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The paper studies resolved systems of language equations that allow the use of all Boolean operations in addition to concatenation. Existence and uniqueness of solutions are shown to be their nontrivial properties, these properties are given characterizations by first order formulae, and the position of the corresponding decision problems in the arithmetical hierarchy is determined. The class of languages defined by components of unique solutions of such systems is shown to coincide with the class of recursive languages.