CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt172",{id:"formSmash:upper:j_idt172",widgetVar:"widget_formSmash_upper_j_idt172",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt179_j_idt182",{id:"formSmash:upper:j_idt179:j_idt182",widgetVar:"widget_formSmash_upper_j_idt179_j_idt182",target:"formSmash:upper:j_idt179:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

An extension of the PPSZ Algorithm to Infinite-Domain Constraint Satisfaction ProblemsPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
##### Abstract [en]

##### Place, publisher, year, edition, pages

2017. , p. 44
##### Keyword [en]

CSP, Algorithms
##### National Category

Computer Sciences
##### Identifiers

URN: urn:nbn:se:liu:diva-141600ISRN: LIU-IDA/LITH-EX-A--17/046--SEOAI: oai:DiVA.org:liu-141600DiVA, id: diva2:1146285
##### Subject / course

Computer science
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt603",{id:"formSmash:j_idt603",widgetVar:"widget_formSmash_j_idt603",multiple:true});
##### Supervisors

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt611",{id:"formSmash:j_idt611",widgetVar:"widget_formSmash_j_idt611",multiple:true});
##### Examiners

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt618",{id:"formSmash:j_idt618",widgetVar:"widget_formSmash_j_idt618",multiple:true});
Available from: 2017-10-03 Created: 2017-10-02 Last updated: 2018-01-13Bibliographically approved

En utökning av PPSZ Algoritmen till Oändlig-Domän Constraint Satisfaction Problem (Swedish)

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.

urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1735",{id:"formSmash:j_idt1735",widgetVar:"widget_formSmash_j_idt1735",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1898",{id:"formSmash:lower:j_idt1898",widgetVar:"widget_formSmash_lower_j_idt1898",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1900_j_idt1902",{id:"formSmash:lower:j_idt1900:j_idt1902",widgetVar:"widget_formSmash_lower_j_idt1900_j_idt1902",target:"formSmash:lower:j_idt1900:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});