Decision problems for language equations

DOI10.1016/J.JCSS.2009.08.002zbMath1201.68067OpenAlexW2135734455MaRDI QIDQ972384

Alexander Okhotin

Publication date: 25 May 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2009.08.002

zbMATH Keywords

Boolean operationscomputabilitylanguage equations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (14)

Equations over sets of integers with addition only ⋮ Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On the expressive power of univariate equations over sets of natural numbers ⋮ Complexity of equations over sets of natural numbers ⋮ On Language Decompositions and Primality ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ Computational completeness of equations over sets of natural numbers ⋮ Representing hyper-arithmetical sets by equations over sets of integers ⋮ Least and greatest solutions of equations over sets of integers ⋮ ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS ⋮ Language equations with complementation: expressive power ⋮ Language equations ⋮ Unresolved systems of language equations: expressive power and decision problems

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On equations for regular languages, finite automata, and sequential networks
• Maximal and minimal solutions to language equations
• Reversal-bounded multipushdown machines
• Set constraints in some equational theories
• Unrestricted complementation in language equations over a one-letter alphabet
• Conjunctive grammars and systems of language equations
• Closure and decidability properties of some language classes with respect to ciliate bio-operations.
• Language equations, maximality and error-detection
• Conway's problem for three-word sets.
• Boolean grammars
• Domain mu-calculus
• Two Families of Languages Related to ALGOL
• The Equivalence Problem of Finite Substitutions on ab*c, with Applications
• Unification of concept terms in description logics

This page was built for publication: Decision problems for language equations