Journal article icon

Journal article

The complexity of maximal constraint languages

Abstract:

Many combinatorial search problems can be expressed as "constraint satisfaction problems" using an appropriate "constraint language", that is, a set of relations over some fixed finite set of values. It is well-known that there is a trade-off between the expressive power of a constraint language and the complexity of the problems it can express. In the present paper we systematically study the complexity of all maximal constraint languages, that is, languages whose expressive power is just we...

Expand abstract

Actions


Authors


Bulatov, A More by this author
Krokhin, A More by this author
Jeavons, P More by this author
Journal:
Conference Proceedings of the Annual ACM Symposium on Theory of Computing
Pages:
667-674
Publication date:
2001
ISSN:
0734-9025
URN:
uuid:001f26b9-4375-4b5c-8153-4db108be106e
Source identifiers:
328404
Local pid:
pubs:328404

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP