Palestrante: Gérard Ligozat

Título: Three Decades of Qualitative Spatial and Temporal Reasoning

Resumo:Allen's 1983 paper on temporal reasoning was seminal in introducing
constraint-satisfaction techniques into qualitative temporal
reasoning. The last three decades have witnessed a series of studies
of the properties of Allen's formalism, as well as an impressive
development of qualitative calculi for reasoning about time and space
based on or inspired by Allen's calculus.

A major theme in the domain has been the study of complexity
properties and the search for tractable, i.e. polynomial, classes. To
this effect, two main approaches have been used: a syntactic one and a
geometic one. Moreover, the definition of a general framework, based
on the notion of partition scheme, to characterize the notion of a
qualitative calculus, has led to a better understanding of the calculi
and to clarifying questions such as the expressiveness properties and
the nature of the models of those calculi. The connection to the
domain of constraint satisfaction problems (CSPs) has been used in
various ways, both for elucidating formal questions as well as for
devising efficient solving methods. Several extensions, including
fuzzy versions of the calculi, have been developed.

Starting with a description of Allen's original calculus considered
from the present perspective, our talk will present the main lines of
development of the domain, as well as some directions for further
research.