Professor Andrei Krokhin andrei.krokhin@durham.ac.uk
Professor
Solving order constraints in logarithmic space
Krokhin, A.; Larose, B.
Authors
B. Larose
Contributors
H. Alt
Editor
M. Habib
Editor
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). Solving order constraints in logarithmic space. In H. Alt, & M. Habib (Eds.), 20th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2003, 27 February-1 March 1 2003 ; proceedings (379-390). https://doi.org/10.1007/3-540-36494-3_34
Conference Name | Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science {(STACS'03) Berlin |
---|---|
Conference Location | Berlin |
Publication Date | Mar 1, 2003 |
Deposit Date | Mar 29, 2010 |
Publicly Available Date | Apr 6, 2010 |
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 |
Files
Accepted Conference Proceeding
(230 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/3-540-36494-3_34
You might also like
Topology and adjunction in promise constraint satisfaction
(2023)
Journal Article
Algebraic Approach to Promise Constraint Satisfaction
(2021)
Journal Article
Robust algorithms with polynomial loss for near-unanimity CSPs
(2019)
Journal Article
Algebraic approach to promise constraint satisfaction
(2019)
Conference Proceeding
Towards a characterization of constant-factor approximable Finite-Valued CSPs
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search