LSV Seminar
The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
Past Seminars
A tetrachotomy for positive equality-free logic
- Date
- Monday, March 12 2012 at 02:00PM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Barnaby Martin (Durham University, UK)
We consider the problem of evaluating positive equality-free sentences of FO on a fixed, finite relational structure B. This may be seen as a generalisation of the Quantified Constraint Satisfaction Problem (QCSP), itself a generalisation of the Constraint Satisfaction Problem (CSP). We argue that our generalisation is not totally arbitrary, and that ours is the only problem in a large class - other than the CSP and QCSP - whose complexity taxonomy was unsolved.
We introduce surjective hyper-endomorphisms in order to give a Galois connection that characterises definability in positive equality-free FO. Through the algebraic method we are able to characterise the complexity of our problem for all finite structures B. Specifically, the problem is either in Logspace, NP-complete, co-NP-complete or Pspace-complete.
The problem appears obtuse, but possesses a surprising elegance. There may yet be lessons to be learnt in the methodology of the solution of this case, for the continuing program for CSP.