Outputs (70)

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.

Extending the Point Algebra into the Qualitative Algebra (2002)
Presentation / Conference Contribution
Krokhin, A., & Jonsson, P. (2002, December). Extending the Point Algebra into the Qualitative Algebra. Presented at Proceedings of 9th International Workshop on Temporal Representation and Reasoning ({TIME'02})

The complexity of constraints on intervals and lengths (2002)
Presentation / Conference Contribution
Krokhin, A., Jeavons, P., & Jonsson, P. (2002, December). The complexity of constraints on intervals and lengths. Presented at Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science {(STACS'02)

A monoidal interval of isotone clones on a finite chain (2002)
Journal Article
Krokhin, A., & Larose, B. (2002). A monoidal interval of isotone clones on a finite chain. Acta scientiarum mathematicarum, 68(1-2), 37-62

Let k denote a k-element chain, k3. Let M denote the clone generated by all unary isotone operations on k and let Pol denote the clone of all isotone operations on k. We investigate the interval of clones [MPol]. Among other results, we describe comp... Read More about A monoidal interval of isotone clones on a finite chain.

On clones, transformation monoids and finite Boolean algebras (2001)
Journal Article
Krokhin, A. (2001). On clones, transformation monoids and finite Boolean algebras. Algebra Universalis, 46(1-2), 231-236

On the structure of clone lattices, II (2001)
Presentation / Conference Contribution
Bulatov, A., Krokhin, A., Safin, K., Semigrodskikh, A., & Sukhanov, E. (2001, December). On the structure of clone lattices, II

On clones preserving a reflexive binary relation (2001)
Journal Article
Krokhin, A., & Schweigert, D. (2001). On clones preserving a reflexive binary relation. Acta scientiarum mathematicarum, 67(3-4), 461-473

A complete classification of complexity in Allen's algebrain the presence of a non-trivial basic relation (2001)
Presentation / Conference Contribution
Krokhin, A., Jeavons, P., & Jonsson, P. (2001, December). A complete classification of complexity in Allen's algebrain the presence of a non-trivial basic relation. Presented at 17th International Joint Conference on Artificial Intelligence, {(IJCAI'01)

Congruences of clone lattices, II (2001)
Journal Article
Krokhin, A. (2001). Congruences of clone lattices, II. Order, 18(2), 151-159

The complexity of maximal constraint languages (2001)
Presentation / Conference Contribution
Bulatov, A., Krokhin, A., & Jeavons, P. (2001, December). The complexity of maximal constraint languages. Presented at 33rd ACM Symposium on the Theory of Computing(STOC), Crete, Greece

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... Read More about The complexity of maximal constraint languages.