Computational completeness of equations over sets of natural numbers

DOI10.1016/j.ic.2014.05.001zbMath1291.03078OpenAlexW2086162968MaRDI QIDQ2252522

Alexander Okhotin, Artur Jeż

Publication date: 18 July 2014

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2014.05.001

zbMATH Keywords

computabilitylanguage equationsunary languages

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Recursively (computably) enumerable sets and degrees (03D25)

Related Items

Equations over sets of integers with addition only, Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic, Circuit satisfiability and constraint satisfaction around Skolem arithmetic, Unambiguous conjunctive grammars over a one-symbol alphabet, Least and greatest solutions of equations over sets of integers, Language equations

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of equations over sets of natural numbers
• One-nonterminal conjunctive grammars over a unary alphabet
• Representing hyper-arithmetical sets by equations over sets of integers
• Unresolved systems of language equations: expressive power and decision problems
• Decision problems for language equations
• 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
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Set constraints with projections
• Systolic trellis automatat†
• Equations between Regular Terms and an Application to Process Logic
• Automatic Sequences
• On the equivalence of linear conjunctive grammars and trellis automata
• Mathematical Foundations of Computer Science 2005
• Two Families of Languages Related to ALGOL
• Unification of concept terms in description logics