Complexity of equations over sets of natural numbers

DOI10.1007/S00224-009-9246-YzbMATH Open1209.68263OpenAlexW2005335312MaRDI QIDQ633764FDOQ633764

Authors: 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

Recommendations

• scientific article; zbMATH DE number 6146470
• On the Computational Completeness of Equations over Sets of Natural Numbers
• Computational completeness of equations over sets of natural numbers
• Conjunctive grammars and equations over sets of natural numbers
• Equations over sets of natural numbers with addition only

zbMATH Keywords

computational complexitylanguage equationsconjunctive grammarsEXPTIME-completenessinteger expressions

Mathematics Subject Classification ID

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

Cites Work

• Alternation
• Title not available (Why is that?)
• Complete problems for deterministic polynomial time
• The power of commuting with finite sets of words
• Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth
• The complexity of membership problems for circuits over sets of natural numbers
• CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES
• Title not available (Why is that?)
• Two Families of Languages Related to ALGOL
• 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
• A recognition and parsing algorithm for arbitrary conjunctive grammars.
• Commutative grammars: The complexity of uniform word problems
• Title not available (Why is that?)
• A PTIME-complete matching problem for SLP-compressed words
• Word Problems and Membership Problems on Compressed Words
• Sparse hard sets for P: Resolution of a conjecture of Hartmanis
• Equivalence Problems for Circuits over Sets of Natural Numbers
• Title not available (Why is that?)
• The Complexity of Membership Problems for Circuits over Sets of Positive Numbers
• Integer circuit evaluation is PSPACE-complete

Cited In (17)

• Parsing Boolean grammars over a one-letter alphabet using online convolution
• Title not available (Why is that?)
• One-nonterminal conjunctive grammars over a unary alphabet
• Expressive power of \(\text{LL}(k)\) Boolean grammars
• Title not available (Why is that?)
• Equations over sets of integers with addition only
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Representing hyper-arithmetical sets by equations over sets of integers
• The complexity of compressed membership problems for finite automata
• Language equations
• Circuit Satisfiability and Constraint Satisfaction Around Skolem Arithmetic
• Computational completeness of equations over sets of natural numbers
• Formal languages over GF(2)
• Unambiguous conjunctive grammars over a one-symbol alphabet
• Parsing by matrix multiplication generalized to Boolean grammars
• Least and greatest solutions of equations over sets of integers

Uses Software

• ALGOL 60

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633764)