Unresolved systems of language equations: expressive power and decision problems
From MaRDI portal
Publication:817804
DOI10.1016/j.tcs.2005.07.038zbMath1086.68077OpenAlexW2070863577MaRDI QIDQ817804
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
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
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
