Quantifier elimination for counting extensions of Presburger arithmetic

DOI10.1007/978-3-030-99253-8_12MaRDI QIDQ6181930zbMATH OpenOpenAlexFDO

Authors Dmitry Chistikov, Christoph Haase, Alessio Mansutti

Publication date 23 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/978-3-030-99253-8_12

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• On Presburger arithmetic extended with modulo counting quantifiers
• Effective Quantifier Elimination for Presburger Arithmetic with Infinity
• scientific article; zbMATH DE number 1253963
• Parametric Presburger arithmetic: complexity of counting and quantifier elimination
• Arithmetic, first-order logic, and counting quantifiers

Cites work

• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed
• Arithmetic, first-order logic, and counting quantifiers
• Axiomatische Untersuchungen über Einige mit der Presburgerschen Arithmetik Verwandte Systeme
• Monadic decomposition
• Monadic decomposition in integer linear arithmetic
• On Presburger arithmetic extended with modulo counting quantifiers
• The complexity of almost linear diophantine problems
• The complexity of logical theories
• The Härtig quantifier: a survey
• Theory of computation.

Cited in

(3)

• On Presburger arithmetic extended with non-unary counting quantifiers
• The complexity of separability for semilinear sets and Parikh automata
• One-parametric Presburger arithmetic has quantifier elimination

This page was built for publication: Quantifier elimination for counting extensions of Presburger arithmetic

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