Presburger arithmetic with algebraic scalar multiplications

MaRDI QIDQ5155665zbMATH OpenFDO

Authors Philipp Hieronymi, Danny Nguyen, Igor Pak

Publication date 8 October 2021

Full work available at URL https://arxiv.org/abs/1805.03624, https://lmcs.episciences.org/7688

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Recommendations

• On Presburger arithmetic extended with modulo counting quantifiers
• Short Presburger Arithmetic Is Hard
• Subclasses of Presburger arithmetic and the polynomial-time hierarchy
• Complexity of Subcases of Presburger Arithmetic
• Presburger arithmetic with bounded quantifier alternation

Cites work

• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• Automata theory and its applications
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Complexity of Subcases of Presburger Arithmetic
• Expansions of dense linear orders with the intermediate value property
• Expansions of the ordered additive group of real numbers by two discrete subgroups
• Finite Automata and the Analysis of Infinite Transition Systems
• scientific article; zbMATH DE number 4204116 (Why is no real title available?)
• scientific article; zbMATH DE number 3501006 (Why is no real title available?)
• scientific article; zbMATH DE number 3510287 (Why is no real title available?)
• scientific article; zbMATH DE number 1253963 (Why is no real title available?)
• scientific article; zbMATH DE number 1027768 (Why is no real title available?)
• scientific article; zbMATH DE number 3001281 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 3408928 (Why is no real title available?)
• Integer optimization on convex semialgebraic sets
• Integer Programming with a Fixed Number of Variables
• Interpreting the projective hierarchy in expansions of the real line
• NP-complete decision problems for binary quadratics
• Ostrowski numeration systems, addition, and finite automata
• Presburger arithmetic with bounded quantifier alternation
• Small fast universal Turing machines
• The complexity of generating functions for integer points in polyhedra and beyond
• The complexity of logical theories
• The Complexity of Translating Logic to Finite Automata
• When is scalar multiplication decidable?

Cited in

(5)

• When is scalar multiplication decidable?
• Short Presburger Arithmetic Is Hard
• Presburger Arithmetic with algebraic scalar multiplications
• Decidability bounds for Presburger arithmetic extended by sine
• Decidability for Sturmian words

This page was built for publication: Presburger arithmetic with algebraic scalar multiplications

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