Complexity of equations over sets of natural numbers

DOI10.1007/s00224-009-9246-yzbMath1209.68263OpenAlexW2005335312MaRDI QIDQ633764

Artur Jeż, Alexander Okhotin

Publication date: 30 March 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-009-9246-y

zbMATH Keywords

computational complexitylanguage equationsconjunctive grammarsEXPTIME-completenessinteger expressions

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (15)

Equations over sets of integers with addition only ⋮ Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic ⋮ Circuit satisfiability and constraint satisfaction around Skolem arithmetic ⋮ Parsing by matrix multiplication generalized to Boolean grammars ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ One-nonterminal conjunctive grammars over a unary alphabet ⋮ Unambiguous conjunctive grammars over a one-symbol alphabet ⋮ Computational completeness of equations over sets of natural numbers ⋮ Representing hyper-arithmetical sets by equations over sets of integers ⋮ The complexity of compressed membership problems for finite automata ⋮ Parsing Boolean grammars over a one-letter alphabet using online convolution ⋮ Expressive power of \(\text{LL}(k)\) Boolean grammars ⋮ Formal languages over GF(2) ⋮ 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
• Unresolved systems of language equations: expressive power and decision problems
• The complexity of membership problems for circuits over sets of integers
• Decision problems for language equations
• The hardest linear conjunctive language
• Complete problems for deterministic polynomial time
• Sparse hard sets for P: Resolution of a conjecture of Hartmanis
• A recognition and parsing algorithm for arbitrary conjunctive grammars.
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• A PTIME-complete matching problem for SLP-compressed words
• The complexity of membership problems for circuits over sets of natural numbers
• The power of commuting with finite sets of words
• Commutative grammars: The complexity of uniform word problems
• Equivalence Problems for Circuits over Sets of Natural Numbers
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Alternation
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• Word Problems and Membership Problems on Compressed Words
• Two Families of Languages Related to ALGOL
• Integer circuit evaluation is PSPACE-complete

This page was built for publication: Complexity of equations over sets of natural numbers