# 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.