ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS

DOI10.1142/S012905411100809XzbMath1209.68301MaRDI QIDQ3086245

Alexander Okhotin, Tommi Lehtinen

Publication date: 30 March 2011

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

language equationsunary languages

Mathematics Subject Classification ID

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

Related Items (5)

Equations over sets of integers with addition only ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ Representing hyper-arithmetical sets by equations over sets of integers ⋮ Least and greatest solutions of equations over sets of integers ⋮ Language equations

Cites Work

• Unresolved systems of language equations: expressive power and decision problems
• Language equations with complementation: decision problems
• Decision problems for language equations
• Elementary induction on abstract structures
• Set constraints in some equational theories
• Unrestricted complementation in language equations over a one-letter alphabet
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• The complexity of membership problems for circuits over sets of natural numbers
• The power of commuting with finite sets of words

This page was built for publication: ON EQUATIONS OVER SETS OF NUMBERS AND THEIR LIMITATIONS