Manuel Bodirsky

Reasoning with temporal relations

Project description

Temporal constraint satisfaction problems have applications in several areas in computer science, for example in scheduling and artificial intelligence. In a temporal constraint satisfaction problem, we are given a set of variables and a set of temporal constraints (an example of a temporal constraint on three variables x,y,z might be "x < y or x < z"), and the task is to determine whether we can map the variables to the rational numbers such that all constraints are satisfied. Depending on the constraint language that we are allowed to use to formulate the constraints, this problem might be efficiently solvable or computationally hard.

The notion of primitive positive definability is a crucial concept to study whether a temporal constraint satisfaction problem is hard or whether it can be solved efficiently. Unfortunately, it is not known whether primitive positive definability of temporal relations is decidable. However, for many fixed temporal constraint languages primitive positive definability of a given relation is indeed decidable.

Goals

Implementation and extension of known procedures for deciding primitive positive definability of temporal relations. Development of a toolkit to efficiently process and manipulate temporal relations.

Prerequisites

Candidates for this project should have some algorithmic experience; logic knowledge is welcome, but not obligatory.

Print version

A project description in pdf.