The Library
Solving order constraints in logarithmic space
Tools
UNSPECIFIED (2003) Solving order constraints in logarithmic space. In: 20th Annual Symposium on Theoretical Aspects of Computer Science, BERLIN, GERMANY, FEB 27-MAR 01, 2003. Published in: STACS 2003, PROCEEDINGS, 2607 pp. 379-390. ISBN 3-540-00623-0. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Series Name: | LECTURE NOTES IN COMPUTER SCIENCE | ||||
Journal or Publication Title: | STACS 2003, PROCEEDINGS | ||||
Publisher: | SPRINGER-VERLAG BERLIN | ||||
ISBN: | 3-540-00623-0 | ||||
ISSN: | 0302-9743 | ||||
Editor: | Alt, H and Habib, M | ||||
Official Date: | 2003 | ||||
Dates: |
|
||||
Volume: | 2607 | ||||
Number of Pages: | 12 | ||||
Page Range: | pp. 379-390 | ||||
Publication Status: | Published | ||||
Title of Event: | 20th Annual Symposium on Theoretical Aspects of Computer Science | ||||
Location of Event: | BERLIN, GERMANY | ||||
Date(s) of Event: | FEB 27-MAR 01, 2003 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |