LFCS Seminar: Barnaby Martin
A tetrachotomy for positive equalityfree logic
What 


When 
Sep 11, 2012 from 04:00 PM to 05:00 PM 
Where  IF 2.33 (TBC) 
Add event to calendar 
vCal iCal 
We consider the problem of evaluating positive equalityfree 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 hyperendomorphisms in order to give a Galois connection that characterises definability in positive equalityfree 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, NPcomplete, coNPcomplete or Pspacecomplete.
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.