2012 (English)Conference paper (Other academic)
The following result for finite structures Gamma has been conjectured to hold for all countably infinite omega-categorical structures Gamma: either the model-complete core Delta of Gamma has an expansion by finitely many constants such that the pseudovariety generated by its polymorphism algebra contains a two-element algebra all of whose operations are projections, or there is a homomorphism f from Delta^k to Delta, for some finite k, and an automorphism alpha of Delta satisfying f(x1,...,xk) = alpha(f(x2,...,xk,x1)). This conjecture has been confirmed for all infinite structures Gamma that have a first-order definition over (Q;<), and for all structures that are definable over the random graph. In this paper, we verify the conjecture for all structures that are definable over an equivalence relation with a countably infinite number of countably infinite classes. Our result implies a complexity dichotomy (into NP-complete and P) for a family of constraint satisfaction problems (CSPs) which we call equivalence constraint satisfaction problems. The classification for equivalence CSPs can also be seen as a first step towards a classification of the CSPs for all relational structures that are first-order definable over Allen's interval algebra, a well-known constraint calculus in temporal reasoning.
Place, publisher, year, edition, pages
2012. 122-136 p.
IdentifiersURN: urn:nbn:se:liu:diva-79516DOI: 10.4230/LIPIcs.CSL.2012.122ISBN: 978-3-939897-42-2OAI: oai:DiVA.org:liu-79516DiVA: diva2:543177
21st EACSL Annual Conference on Computer Science Logic (CSL-2012),3-6 September, Fontainebleau, France