The One-Variable Logic Meets Presburger Arithmetic

10/25/2018
by   Bartosz Bednarczyk, et al.
0

We consider the one-variable fragment of first-order logic extended with Presburger constraints. The logic is designed in such a way that it subsumes the previously-known fragments extended with counting, modulo counting or cardinality comparison and combines their expressive power. We prove NP-completeness of the logic by presenting an optimal algorithm for solving its finite satisfiability problem.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset