The complexity of the equivalence problem for two characterizations of Presburger sets

DOI10.1016/S0304-3975(81)80003-5zbMath0454.03005MaRDI QIDQ1149429

Oscar H. Ibarra, Eitan M. Gurari

Publication date: 1981

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

upper boundsemilinear setsPresburger formulasreversal-bounded multicounter machinesdeterministic time complexityinequivalence problemPresburger relations

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (4)

Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES ⋮ Descriptional Complexity of Two-Way Pushdown Automata with Restricted Head Reversals ⋮ Some classes of languages in \(NC^ 1\)

Cites Work

• Simple counter machines and number-theoretic problems
• Hierarchies of complete problems
• Reversal-bounded multipushdown machines
• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• Semigroups, Presburger formulas, and languages
• A characterization of semilinear sets
• Bounds on Positive Integral Solutions of Linear Diophantine Equations
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• An NP-complete number-theoretic problem
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of the equivalence problem for two characterizations of Presburger sets