A fundamental problem in the eld of Arti cial Intelligence and related disciplines, in particular Database theory, is the constraint satisfaction problem (or CSP) which comes as a unifying framework to express a wide spectrum of computational problems. Examples include graph colorability, planning, and database queries. The goal is either to nd one solution, to enumerate all solutions, or counting them. As a very general problem, it comes with no surprise that in most settings CSPs are hard to solve. Indeed considerable e ort has been invested by the scienti c community to shed light on the computational issues of this problem, with the objective of identifying easy instances (also called islands of tractability) and exploiting the knowledge derived from their solution to help solving the harder ones. My thesis investigates the role that structural properties play in the computational aspects of CSPs, describes algorithms to exploit such properties, and provides a number of speci c tools to solve e ciently problems arising in database theory, game theory, and process mining.

Constraint satisfaction: algorithms, complexity results, and applications

2016

Abstract

A fundamental problem in the eld of Arti cial Intelligence and related disciplines, in particular Database theory, is the constraint satisfaction problem (or CSP) which comes as a unifying framework to express a wide spectrum of computational problems. Examples include graph colorability, planning, and database queries. The goal is either to nd one solution, to enumerate all solutions, or counting them. As a very general problem, it comes with no surprise that in most settings CSPs are hard to solve. Indeed considerable e ort has been invested by the scienti c community to shed light on the computational issues of this problem, with the objective of identifying easy instances (also called islands of tractability) and exploiting the knowledge derived from their solution to help solving the harder ones. My thesis investigates the role that structural properties play in the computational aspects of CSPs, describes algorithms to exploit such properties, and provides a number of speci c tools to solve e ciently problems arising in database theory, game theory, and process mining.
19-feb-2016
Inglese
Artificial intelligence
Computational complexity
Crupi, Felice
Scarcello, Francesco
Greco, Gianluigi
Università della Calabria
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in UNITESI sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14242/147999
Il codice NBN di questa tesi è URN:NBN:IT:UNICAL-147999