Showing cs.LOShow all
3 papers · 1 filter
cs.LO2026
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…
cs.LO2026
Tighter Bounds for Query Answering with Guarded TGDs
Antoine Amarilli, Michael Benedikt
We consider the complexity of the open-world query answering problem, where we wish to determine certain answers to conjunctive queries over incomplete datasets specified by an ini…
cs.LO2024
Embedded Finite Models Beyond Restricted Quantifier Collapse
Michael Benedikt, Ehud Hrushovski
We revisit evaluation of logical formulas that allow both uninterpreted relations, constrained to be finite, as well as an interpreted vocabulary over an infinite domain. This form…