Constraint satisfaction and semilinear expansions of addition over the rationals and the reals

Autor: Peter Jonsson, Johan Thapper
Přispěvatelé: Department of Computer and Information Science - Linköping University, Linköping University (LIU), Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM)
Jazyk: angličtina
Rok vydání: 2016
Předmět:
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
FOS: Computer and information sciences
Rational number
Computer and Information Sciences
Computational complexity theory
Constraint satisfaction problems
Computer Networks and Communications
Semilinear sets
Algorithms
Computational complexity
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0102 computer and information sciences
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Computational Complexity (cs.CC)
01 natural sciences
Theoretical Computer Science
Integer
0101 mathematics
Time complexity
Finite set
Constraint satisfaction problem
Mathematics
Discrete mathematics
Applied Mathematics
010102 general mathematics
Solution set
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
Data- och informationsvetenskap
Computational complexity * Corresponding author
Constraint satisfaction
Computer Science - Computational Complexity
Computational Theory and Mathematics
010201 computation theory & mathematics
Zdroj: Journal of Computer and System Sciences
Journal of Computer and System Sciences, Elsevier, 2016, 82 (5), pp.912-928. ⟨10.1016/j.jcss.2016.03.002⟩
ISSN: 0022-0000
1090-2724
Popis: 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) | x+y=z}
22 pages, 1 figure
Databáze: OpenAIRE
Externí odkaz: