Krokhin, A. and Larose, B. (2003) 'Solving order constraints in logarithmic space.', in 20th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2003, 27 February-1 March 1 2003 ; proceedings. Berlin ; Heidelberg: Springer, pp. 379-390. Lecture notes in computer science. (2607).
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.
|Item Type:||Book chapter|
|Full text:||(AM) Accepted Manuscript|
Download PDF (225Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/3-540-36494-3_34|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/3-540-36494-3_34|
|Date accepted:||No date available|
|Date deposited:||06 April 2010|
|Date of first online publication:||January 2003|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|