Logics with Counting and Equivalence
Author: Ian Pratt-Hartmann
Paper Information
| Title: | Logics with Counting and Equivalence |
| Authors: | Ian Pratt-Hartmann |
| Proceedings: | CSL-LICS 2014 Full and Final Proceedings |
| Editors: | Dale Miller and Laura Kovacs |
| Keywords: | first-order logic, counting quantifiers, equivalence relation, satisfiability, complexity |
| Abstract: | ABSTRACT. We consider the two-variable fragment of first-order logic with counting quantifiers, subject to the stipulation that a single distinguished binary predicate be interpreted as an equivalence. We show that the satisfiability and finite satisfiability problems for this logic are both NExpTime-complete. |
| Pages: | 10 |
| Talk: | Jul 15 15:00 |
| Paper: |  |