Solving order constraints in logarithmic space

Krokhin, A.; Larose, B.

Abstract

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 on a poset which guarantee solvability of the problems in (deterministic, symmetric, or non-deterministic) logarithmic space. On the example of order constraints we study how a certain algebraic invariance property is related to solvability of a constraint satisfaction problem in non-deterministic logarithmic space.

Citation

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

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science {(STACS'03) Berlin
• Publication Date: Mar 1, 2003
• Deposit Date: Mar 29, 2010
• Publicly Available Date: Apr 6, 2010
• Print ISSN: 0302-9743
• Publisher: Springer Verlag
• Pages: 379-390
• Series Title: Lecture notes in computer science
• Series Number: 2607
• Book Title: 20th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2003, 27 February-1 March 1 2003 ; proceedings.
• ISBN: 9783540006237
• DOI: https://doi.org/10.1007/3-540-36494-3_34
• Public URL: https://durham-repository.worktribe.com/output/1162345