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

Combinatorial Slice TheoryPrimeFaces.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}); 2013 (English)Doctoral thesis, monograph (Other academic)
##### Abstract [en]

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

Stockholm: KTH Royal Institute of Technology, 2013. , viii, 195 p.
##### Keyword [en]

Combinatorial Slice Theory, Partial Order Theory of Concurrency, Digraph Width Measures, Equational Logic
##### National Category

Computer Science
##### Identifiers

URN: urn:nbn:se:kth:diva-134211ISBN: 978-91-7501-933-8 (print)OAI: oai:DiVA.org:kth-134211DiVA: diva2:665450
##### Public defence

2013-12-12, F3, Lindtedtsvägen 26, KTH, Stockholm, 10:00 (English)
##### Opponent

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt482",{id:"formSmash:j_idt482",widgetVar:"widget_formSmash_j_idt482",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt488",{id:"formSmash:j_idt488",widgetVar:"widget_formSmash_j_idt488",multiple:true});
##### Funder

EU, European Research Council, 269335 MBAT
##### Note

Slices are digraphs that can be composed together to form larger digraphs.In this thesis we introduce the foundations of a theory whose aim is to provide ways of defining and manipulating infinite families of combinatorial objects such as graphs, partial orders, logical equations etc. We give special attentionto objects that can be represented as sequences of slices. We have successfully applied our theory to obtain novel results in three fields: concurrency theory,combinatorics and logic. Some notable results are:

- Concurrency Theory:

- We prove that inclusion and emptiness of intersection of the causalbehavior of bounded Petri nets are decidable. These problems had been open for almost two decades.
- We introduce an algorithm to transitively reduce infinite familiesof DAGs. This algorithm allows us to operate with partial order languages defined via distinct formalisms, such as, Mazurkiewicztrace languages and message sequence chart languages.

- Combinatorics:

- For each constant z ∈ N, we define the notion of z-topological or-der for digraphs, and use it as a point of connection between the monadic second order logic of graphs and directed width measures, such as directed path-width and cycle-rank. Through this connection we establish the polynomial time solvability of a large numberof natural counting problems on digraphs admitting z-topological orderings.

- Logic:

- We introduce an ordered version of equational logic. We show thatthe validity problem for this logic is fixed parameter tractable withrespect to the depth of the proof DAG, and solvable in polynomial time with respect to several notions of width of the equations being proved. In this way we establish the polynomial time provability of equations that can be out of reach of techniques based on completion and heuristic search.

QC 20131120

Available from: 2013-11-20 Created: 2013-11-19 Last updated: 2013-11-20Bibliographically approved
isbn
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1204",{id:"formSmash:j_idt1204",widgetVar:"widget_formSmash_j_idt1204",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

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