Analysis of logics with arithmetic

Abstract

We present new results on finite satisfiability of logics with counting and arithmetic. This includes tight bounds on the complexity for two-variable logic with counting and cardinality comparisons between unary formulas, and also on logics with so-called local Presburger quantifiers. In the process, we provide simpler proofs of some key prior results on finite satisfiability and semi-linearity of the spectrum for these logics.

Categories