7 citations · 32 across the 13 of their papers we have counts for
3 papers · 1 filter
The complexity of Presburger arithmetic with power or powers
Michael Benedikt, Dmitry Chistikov, Alessio Mansutti
We investigate expansions of Presburger arithmetic, i.e., the theory of the integers with addition and order, with additional structure related to exponentiation: either a function…
Presburger arithmetic with threshold counting quantifiers is easy
Dmitry Chistikov, Christoph Haase, Alessio Mansutti
We give a quantifier elimination procedures for the extension of Presburger arithmetic with a unary threshold counting quantifier that determines whether the nu…
Approximate Counting in SMT and Value Estimation for Probabilistic Programs
Dmitry Chistikov, Rayna Dimitrova, Rupak Majumdar
#SMT, or model counting for logical theories, is a well-known hard problem that generalizes such tasks as counting the number of satisfying assignments to a Boolean formula and com…