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-Verlag, 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:||PDF - Accepted Version (225Kb)|
|Publisher Web site:||http://dx.doi.org/10.1007/3-540-36494-3_34|
|Publisher statement:||The original publication is available at www.springerlink.com|
|Record Created:||29 Mar 2010 14:05|
|Last Modified:||14 Dec 2011 09:56|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|