Outputs (69)

Complexity classification in qualitative temporal constraint reasoning (2004)
Journal Article
Jonsson, P., & Krokhin, A. (2004). Complexity classification in qualitative temporal constraint reasoning. Artificial Intelligence, 160(1-2), 35-51. https://doi.org/10.1016/j.artint.2004.05.010

We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allen's interval algebra. We identify all tractable fragments and show that ever... Read More about Complexity classification in qualitative temporal constraint reasoning.

A maximal tractable class of soft constraints (2004)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2004). A maximal tractable class of soft constraints. Journal of Artificial Intelligence Research, 22, 1-22. https://doi.org/10.1613/jair.1400

Many researchers in artificial intelligence are beginning to explore the use of soft constraints to express a set of (possibly conflicting) problem requirements. A soft constraint is a function defined on a collection of variables which associates so... Read More about A maximal tractable class of soft constraints.

Constraint satisfaction problems on intervals and lengths (2004)
Journal Article
Krokhin, A., Jeavons, P., & Jonsson, P. (2004). Constraint satisfaction problems on intervals and lengths. SIAM Journal on Discrete Mathematics, 17(3), 453-477. https://doi.org/10.1137/s0895480102410201

We study interval-valued constraint satisfaction problems (CSPs), in which the aim is to find an assignment of intervals to a given set of variables subject to constraints on the relative positions of intervals. Many well-known problems such as INTER... Read More about Constraint satisfaction problems on intervals and lengths.

First-Order Definable Retraction Problems for Posets and Reflexive Graphs (2004)
Presentation / Conference Contribution
Dalmau, V., Krokhin, A., & Larose, B. (2023, July). First-Order Definable Retraction Problems for Posets and Reflexive Graphs. Presented at 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), Turku, Finland

A retraction from a structure P to its substructure Q is a homomorphism from P onto Q that is the identity on Q. We present an algebraic condition which completely characterises all posets and all reflexive graphs Q with the following property: the c... Read More about First-Order Definable Retraction Problems for Posets and Reflexive Graphs.

Quantified constraints: Algorithms and complexity (2003)
Presentation / Conference Contribution
Boerner, F., Bulatov, A., Jeavons, P., & Krokhin, A. (2003, December). Quantified constraints: Algorithms and complexity. Presented at 17th International Workshop on Computer Science Logic

A tractable class of soft constraints. (2003)
Presentation / Conference Contribution
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2003, December). A tractable class of soft constraints. Presented at 18th International Joint Conference on Artificial Intelligence {(IJCAI'03)

Soft constraints: complexity and multimorphisms (2003)
Presentation / Conference Contribution
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2003, December). Soft constraints: complexity and multimorphisms. Presented at Proceedings of 9th International Conference on Principle and Practice of Constraint Programming {(CP'03)

Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra (2003)
Journal Article
Krokhin, A., Jeavons, P., & Jonsson, P. (2003). Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra. Journal of the ACM, 50(5), 591-640. https://doi.org/10.1145/876638.876639

Allen's interval algebra is one of the best established formalisms for temporal reasoning. This article provides the final step in the classification of complexity for satisfiability problems over constraints expressed in this algebra. When the const... Read More about Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra.

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey (2003)
Presentation / Conference Contribution
Krokhin, A., Bulatov, A., & Jeavons, P. (2003, May). Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. Presented at 33rd International Symposium on Multiple-Valued Logic (ISMVL'03)

Many computational problems arising in artificial intelligence, computer science and elsewhere can be represented as constraint satisfaction and optimization problems. In this short survey we discuss an approach that is related to the algebraic compo... Read More about Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey.

Solving order constraints in logarithmic space (2003)
Presentation / Conference Contribution
Krokhin, A., & Larose, B. (2003, January). Solving order constraints in logarithmic space. Presented at Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science {(STACS'03) Berlin, Berlin

We combine methods of order theory, finite model theory, and universal algebra to study, within the constraint satisfaction framework, the complexity of some well-known combinatorial problems connected with a finite poset. We identify some conditions... Read More about Solving order constraints in logarithmic space.