liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 (print), 1611-3349 (online)
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:liu:diva-112904DOI: 10.1007/978-3-662-44465-8_36ISI: 000358254600036Scopus ID: 2-s2.0-84906239762ISBN: 978-3-662-44464-1 (print)OAI: oai:DiVA.org:liu-112904DiVA: diva2:773660
Conference
39th International Symposium on Mathematical Foundations of Computer Science (MFCS-2014)
Available from: 2014-12-19 Created: 2014-12-19 Last updated: 2017-02-23

Open Access in DiVA

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

Other links

Publisher's full textScopus

Authority records BETA

Jonsson, Peter

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: 30 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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 82 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf