On Presburger arithmetic extended with non-unary counting quantifiers

DOI10.46298/lmcs-19(3:4)2023arXiv2204.03903MaRDI QIDQ6135772

Peter Habermehl, Dietrich Kuske

Publication date: 26 August 2023

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2204.03903

zbMATH Keywords

quantifier eliminationdecision procedurePresburger arithmeticcounting quantifiersnon-unary quantifiers

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Subclasses of Presburger arithmetic and the polynomial-time hierarchy
• The complexity of logical theories
• A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
• The computational complexity of logical theories
• Complexity of Presburger arithmetic with fixed quantifier dimension
• On Presburger Arithmetic Extended with Modulo Counting Quantifiers
• On Chebyshev-Type Inequalities for Primes
• On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation
• The Härtig quantifier: a survey
• A Bound on Solutions of Linear Integer Equalities and Inequalities
• Subclasses of presburger arithmetic and the weak EXP hierarchy
• Arithmetic, first-order logic, and counting quantifiers
• Bounds on the automata size for Presburger arithmetic
• Presburger arithmetic with bounded quantifier alternation
• Axiomatische Untersuchungen über Einige mit der Presburgerschen Arithmetik Verwandte Systeme
• Quantifier elimination for counting extensions of Presburger arithmetic

This page was built for publication: On Presburger arithmetic extended with non-unary counting quantifiers