Change search

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• 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
An extension of the PPSZ Algorithm to Infinite-Domain Constraint Satisfaction Problems
Linköping University, Department of Computer and Information Science, Software and Systems.
2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
En utökning av PPSZ Algoritmen till Oändlig-Domän Constraint Satisfaction Problem (Swedish)
##### Abstract [en]

The PPSZ algorithm (Paturi et al., FOCS 1998) is the fastest known algorithm for solving k-SAT when k >= 4. Hertli et al. recently extended the algorithm to solve (d, k)-Clause Satisfaction problems ((d,k)-ClSP) for which it is the fastest known algorithm for all k >= 3 (Hertli et al. CP 2016). We analyze their algorithm and extend it to solve problems over an infinite domain. More specifically we show how the extended algorithm can solve problems that have an infinite domain but where we can, for each instance of the problem, find a finite subset of the domain which has the following properties: If there exists a solution to the problem instance, then there exists a solution using only values from this subset and the size of this subset is polynomial in the size of the problem instance. We show numerically that our algorithm is the fastest known for problems over bounded disjunction languages for some values of k <= 500 and we look at the branching time temporal language, which is a bounded disjunction language, to show how to transform a specific problem to (d,k)-ClSP. We also look at Allen's interval algebra but conclude that there is already a faster algorithm for solving this problem.

2017. , p. 44
CSP, Algorithms
##### National Category
Computer Sciences
##### Identifiers
ISRN: LIU-IDA/LITH-EX-A--17/046--SEOAI: oai:DiVA.org:liu-141600DiVA, id: diva2:1146285
Computer science
##### Examiners
Available from: 2017-10-03 Created: 2017-10-02 Last updated: 2018-01-13Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 427 kBChecksum SHA-512
161ee7e5044e8e89b54b2cfbeef351acaf8c84263b19764c3bb0a7e93a8dc30a5ff8fde61a1ac543bb755183072c8af6f4c66c60a5a5c58143acdab34b7e6425
Type fulltextMimetype application/pdf

#### Search in DiVA

Einarson, Carl
##### By organisation
Software and Systems
##### On the subject
Computer Sciences

#### Search outside of DiVA

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
urn-nbn

#### Altmetric score

urn-nbn
Total: 1814 hits

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• 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
v. 2.35.3
|