Change search
ReferencesLink to record
Permanent link

Direct link
Affine Consistency and the Complexity of Semilinear Constraints
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology. (TCSLAB)
Université Paris-Sud 11, Laboratoire de Recherche en Informatique (LRI) .
Number of Authors: 2
2014 (English)In: Mathematical Foundations of Computer Science 2014, Springer Berlin/Heidelberg, 2014, 420-431 p.Conference paper (Refereed)
Abstract [en]

A semilinear relation is a finite union of finite intersections of open and closed half-spaces over, for instance, the reals, the rationals or the integers. Semilinear relations have been studied in connection with algebraic geometry, automata theory, and spatiotemporal reasoning, just to mention a few examples. We concentrate on relations over the reals and rational numbers. Under this assumption, the computational complexity of the constraint satisfaction problem (CSP) is known for all finite sets Γ of semilinear relations containing the relations R +={(x,y,z) | x+y=z}, ≤ and {1}. These problems correspond to extensions of LP feasibility. We generalise this result as follows. We introduce an algorithm, based on computing affine hulls, which solves a new class of semilinear CSPs in polynomial time. This allows us to fully determine the complexity of CSP(Γ) for semilinear Γ containing R+ and satisfying two auxiliary conditions. Our result covers all semilinear Γ such that {R+,{1}}⊆Γ. We continue by studying the more general case when Γ contains R+ but violates either of the two auxiliary conditions. We show that each such problem is equivalent to a problem in which the relations are finite unions of homogeneous linear sets and we present evidence that determining the complexity of these problems may be highly non-trivial.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2014. 420-431 p.
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online)
National Category
Computer and Information Science
URN: urn:nbn:se:liu:diva-112904DOI: 10.1007/978-3-662-44465-8_36ISI: 000358254600036ScopusID: 2-s2.0-84906239762ISBN: 978-3-662-44464-1OAI: diva2:773660
39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014)
Available from: 2014-12-19 Created: 2014-12-19 Last updated: 2015-08-20

Open Access in DiVA

fulltext(308 kB)13 downloads
File information
File name FULLTEXT01.pdfFile size 308 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
Software and SystemsThe Institute of Technology
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 13 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 57 hits
ReferencesLink to record
Permanent link

Direct link