liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Equivalence Constraints
Ecole Polytechnique, Palaiseau, France.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
2012 (English)Conference paper (Other academic)
Abstract [en]

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.
National Category
Computer Science
URN: urn:nbn:se:liu:diva-79516DOI: 10.4230/LIPIcs.CSL.2012.122ISBN: 978-3-939897-42-2OAI: diva2:543177
21st EACSL Annual Conference on Computer Science Logic (CSL-2012),3-6 September, Fontainebleau, France
Available from: 2012-08-06 Created: 2012-08-06 Last updated: 2014-11-11

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Wrona, Michal
By organisation
Software and SystemsThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 30 hits
ReferencesLink to record
Permanent link

Direct link