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

Direct link
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, 912-928 p.Article in journal (Refereed) PublishedText
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, 912-928 p.
Keyword [en]
Constraint satisfaction problems; Semilinear sets; Algorithms; Computational complexity
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:liu:diva-128917DOI: 10.1016/j.jcss.2016.03.002ISI: 000374425900016OAI: oai:DiVA.org:liu-128917DiVA: diva2:934987
Note

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

Available from: 2016-06-09 Created: 2016-06-07 Last updated: 2016-09-15

Open Access in DiVA

The full text will be freely available from 2018-03-17 16:49
Available from 2018-03-17 16:49

Other links

Publisher's full text

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 Science

Search outside of DiVA

GoogleGoogle Scholar
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: 37 hits
ReferencesLink to record
Permanent link

Direct link