On Equations over Sets of Numbers and Their Limitations

DOI10.1007/978-3-642-02737-6_29zbMath1247.68209OpenAlexW1546714647MaRDI QIDQ3637239

Tommi Lehtinen, Alexander Okhotin

Publication date: 7 July 2009

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02737-6_29

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Cites Work

• On the expressive power of univariate equations over sets of natural numbers
• Unresolved systems of language equations: expressive power and decision problems
• Set constraints in some equational theories
• Unrestricted complementation in language equations over a one-letter alphabet
• The complexity of membership problems for circuits over sets of natural numbers
• The power of commuting with finite sets of words
• Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth
• On the Computational Completeness of Equations over Sets of Natural Numbers
• Language Equations with Complementation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On Equations over Sets of Numbers and Their Limitations