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
Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering.
University of Paris Est Marne la Vallee, France.
2016 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, E-ISSN 1090-2724, Vol. 82, no 5, p. 912-928Article in journal (Refereed) Published
Resource type
Text
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. We consider semilinear relations over the rationals and the reals. Under this assumption, the computational complexity of the constraint satisfaction problem (CSP) is known for all finite sets containing R+ = {(x, y, z) vertical bar x y = z}, <=, and {1}. These problems correspond to expansions of the linear programming feasibility problem. We generalise this result and fully determine the complexity for all finite sets of semilinear relations containing R+. This is accomplished in part by introducing an algorithm, based on computing affine hulls, which solves a new class of semilinear CSPs in polynomial time. We further analyse the complexity of linear optimisation over the solution set and the existence of integer solutions. (C) 2016 Elsevier Inc. All rights reserved.

Place, publisher, year, edition, pages
ACADEMIC PRESS INC ELSEVIER SCIENCE , 2016. Vol. 82, no 5, p. 912-928
Keywords [en]
Constraint satisfaction problems; Semilinear sets; Algorithms; Computational complexity
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:liu:diva-128917DOI: 10.1016/j.jcss.2016.03.002ISI: 000374425900016OAI: oai:DiVA.org:liu-128917DiVA, id: diva2:934987
Note

Funding Agencies|Swedish Research Council (VR) [621-2012-3239]

Available from: 2016-06-09 Created: 2016-06-07 Last updated: 2018-01-10

Open Access in DiVA

fulltext(517 kB)1 downloads
File information
File name FULLTEXT01.pdfFile size 517 kBChecksum SHA-512
80a10af131ffde99555d154782e025be6a6623a4b42c7e8e72f3c494c25a6d2e533dc3a4db682c2455bd57a3cb1933527e9e98f928ad08dde739e85e40a9c428
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Jonsson, Peter

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
Software and SystemsFaculty of Science & Engineering
In the same journal
Journal of computer and system sciences (Print)
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 1 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
urn-nbn

Altmetric score

doi
urn-nbn
Total: 52 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