[new date!] Thursday, 23.06, 11:15, 310

posted 12 May 2016, 03:12 by Jakub Michaliszyn   [ updated 14 Jun 2016, 11:52 ]
Lidia Tendera University of Opole

Quine’s Fluted Fragment is Non-elementary

The fluted fragment is a decidable fragment of first-order logic, originally identified by W.V. Quine, in which, roughly speaking,
the order of quantification of variables matches their order of appearance as arguments to predicates. We show that the satisfiability problem for this fragment has non-elementary complexity, thus refuting an earlier published claim by W.C. Purdy that it is in NEXPTIME.

Based on a recent joint work with Ian Pratt-Hartmann and Wiesław Szwast.