Tata Institute of Fundamental Research

Quantifier Elimination in Presburger Arithmetic

STCS Student Seminar
Speaker: Koduri Choudary (TIFR)
Organiser: Varun Ramanathan
Date: Friday, 26 Apr 2024, 14:30 to 15:30
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)

Presburger Arithmetic is the sub-category of First Order Logic, which deals with quantification over Integers, with addition, order relation, and multiplication and divisibility by constants. Our goal is to decide the truth value of sentence of Presburger Arithmetic by eliminating the quantifiers.

Source: Derek C. Oppen, A $2^{2^{2^{pn}}}$ Upper Bound on the Complexity of Presburger Arithmetic, 323-332, Journal of Computer and System Sciences, 1978.