Computational completeness of equations over sets of natural numbers
From MaRDI portal
Publication:2252522
DOI10.1016/j.ic.2014.05.001zbMath1291.03078OpenAlexW2086162968MaRDI QIDQ2252522
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
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
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