Constraint satisfaction problems over the integers with successor

Conference paper

Bodirsky, M., Martin, B. and Mottet, A. 2015. Constraint satisfaction problems over the integers with successor. 42nd ICALP 2015. Kyoto, Japan 06 - 10 Jul 2015 Heidelberg, Germany Springer Berlin. Heidelberg. pp. 256-267 https://doi.org/10.1007/978-3-662-47672-7_21
TypeConference paper
TitleConstraint satisfaction problems over the integers with successor
AuthorsBodirsky, M., Martin, B. and Mottet, A.
Abstract

A distance constraint satisfaction problem is a constraint satisfaction problem (CSP) whose constraint language consists of relations that are first-order definable over (Z;succ) , i.e., over the integers with the successor function. Our main result says that every distance CSP is in P or NP-complete, unless it can be formulated as a finite domain CSP in which case the computational complexity is not known in general.

Research GroupFoundations of Computing group
Conference42nd ICALP 2015
Page range256-267
ISSN0302-9743
Electronic1611-3349
ISBN
Paperback9783662476710
Electronic9783662476727
PublisherSpringer Berlin. Heidelberg
Place of publicationHeidelberg, Germany
Publication dates
Print06 Jul 2015
Online20 Jun 2015
Publication process dates
Deposited03 Jun 2015
Accepted15 Apr 2015
Output statusPublished
Additional information

Paper published in: Automata, Languages, and Programming,
Volume 9134 of the series Lecture Notes in Computer Science, pp 256-267

Digital Object Identifier (DOI)https://doi.org/10.1007/978-3-662-47672-7_21
LanguageEnglish
Book titleAutomata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I
Permalink -

https://repository.mdx.ac.uk/item/858q4

Log in to edit
  • 17
    total views
  • 0
    total downloads
  • 1
    views this month
  • 0
    downloads this month

Export as