UNSPECIFIED (2003) Solving order constraints in logarithmic space. In: 20th Annual Symposium on Theoretical Aspects of Computer Science, FEB 27-MAR 01, 2003, BERLIN, GERMANY.

Full text not available from this repository.

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
Date:	2003
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
URI:	http://wrap.warwick.ac.uk/id/eprint/9751

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item