Super-exponential complexity of Presburger arithmetic

MaRDI QIDQ4391216zbMATH OpenFDO

Authors Michael Fischer, Michael O. Rabin

Publication date 13 September 1998

Mathematics Subject Classification ID

Collected or selected works; reprintings or translations of classics (01A75) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30)

Review text

Reprint from: Complexity of computation, Proc. Symp. Appl. Math., New York City 1973, 27-41 (1974; Zbl 0319.68024). For the entire collection see [Zbl 0906.03033].

Cited in

(8)

• Tarski's influence on computer science
• scientific article; zbMATH DE number 2226428 (Why is no real title available?)
• Between the Rings $${\mathbb Z}/p^n{\mathbb Z}$$ and the Ring $${\mathbb Z}_p$$: Issues of Axiomatizability, Definability and Decidability
• Realizability modulo theories
• Artificial intelligence and inherent mathematical difficulty
• An efficient quantifier elimination procedure for Presburger arithmetic
• Synchronized CTL over one-counter automata
• Superefficiency from the vantage point of computability

This page was built for publication: Super-exponential complexity of Presburger arithmetic

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