Unresolved systems of language equations: expressive power and decision problems

DOI10.1016/j.tcs.2005.07.038zbMath1086.68077OpenAlexW2070863577MaRDI QIDQ817804

Alexander Okhotin

Publication date: 20 March 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.07.038

zbMATH Keywords

decision problemsformal languageslanguage equations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (9)

Equations over sets of integers with addition only ⋮ Language equations with complementation: decision problems ⋮ Complexity of equations over sets of natural numbers ⋮ Computational completeness of equations over sets of natural numbers ⋮ Representing hyper-arithmetical sets by equations over sets of integers ⋮ ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS ⋮ On Equations over Sets of Numbers and Their Limitations ⋮ Language equations ⋮ The dual of concatenation

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
• Decision problems for language equations
• Polynomial operations and hierarchies of concatenation
• Reversal-bounded multipushdown machines
• Constructive versions of Tarski's fixed point theorems
• Unrestricted complementation in language equations over a one-letter alphabet
• Conjunctive grammars and systems of language equations
• Conway's problem for three-word sets.
• Boolean grammars
• Systolic trellis automatata †
• Domain mu-calculus
• On the equivalence of linear conjunctive grammars and trellis automata
• Two Families of Languages Related to ALGOL
• Decidability of Second-Order Theories and Automata on Infinite Trees
• STACS 2005
• Unification of concept terms in description logics

This page was built for publication: Unresolved systems of language equations: expressive power and decision problems