Constraint satisfaction, graphs and algebras Jakub Bulín Abstract This thesis consists of three papers in the area of algebraic approach to the constraint satisfaction problem. In the first paper, a joint work with Deli'c, Jackson and Niven, we study the reduction of fixed template CSPs to digraphs. We construct, for every relational structure A, a digraph D(A) such that CSP(A) and CSP(D(A)) are logspace equivalent and most rele- vant properties carry over from A to D(A). As a consequence, the algebraic conjectures characterizing CSPs solvable in P, NL and L are equivalent to their restrictions to digraphs. In the second paper we prove that, given a core relational structure A of bounded width and B ⊆ A, it is decidable whether B is an absorbing subuniverse of the algebra of polymorphisms of A. As a by-product, we show that Jónsson absorption coincides with the usual absorption in this case. In the third paper we establish, using modern algebraic tools (e.g. absorption theory and pointing operations), the CSP dichotomy conjecture for so-called special oriented trees and in particular prove that all tractable core special trees have bounded width. Keywords: constraint satisfaction problem, algebra of polymorphisms, absorbing subuniverse, bounded width, oriented tree.
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:338069 |
| Date | January 2014 |
| Creators | Bulín, Jakub |
| Contributors | Barto, Libor, Růžička, Pavel, Bulatov, Andrei |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.0013 seconds