Amar Isli

Amar Isli

TCSPs (Temporal Constraint Satisfaction Problems), as defined in [Dechter et al., 1991], get rid of unary constraints by binarizing them after having added an "origin of the world" variable. In this work, we look at the constraints between the "origin of the world" variable and the other variables, as the (binarized) domains of these other variables. With this in mind, we define a notion of arc-consistency for TCSPs, which we will refer to as binarized-domains Arc-Consistency, or bdArc-Consistency for short. We provide an algorithm achieving bdArc-Consistency for a TCSP, which we will refer to as bdAC-3, for it is an adaptation of Mackworth's [1977] well-known arc-consistency algorithm AC-3. We show that if a convex TCSP, referred to in [Dechter et al., 1991] as an STP (Simple Temporal Problem), is bdArc-Consistent, and its "origin of the world" variable disconnected from none of the other variables, its binarized domains are minimal. We provide two polynomial backtrack-free procedures: one for the task of getting, from a bdArc-Consistent STP, either that it is inconsistent or, in case of consistency, a bdArc-Consistent STP refinement whose "origin of the world" variable is disconnected from none of the other variables; the other for the task of getting a solution from a bdArc-Consistent STP whose "origin of the world" variable is disconnected from none of the other variables. We then show how to use our results both in a general TCSP solver and in a TCSP-based job shop scheduler. From our work can be extracted a one-to-all all-to-one shortest paths algorithm of an IR-labelled directed graph. Finally, we show that an existing adaptation to TCSPs of Mackworth's [1977] path-consistency algorithm PC-2 is not guaranteed to always terminate, and correct it.

Amar Isli

The aim of this work is to provide a family of qualitative theories for spatial change in general, and for motion of spatial scenes in particular. To achieve this, we consider a spatio-temporalisation MTALC(Dx), of the well-known ALC(D) family of Description Logics (DLs) with a concrete domain: the MTALC(Dx) concepts are interpreted over infinite k-ary Sigma-trees, with the nodes standing for time points, and Sigma including, additionally to its uses in classical k-ary Sigma-trees, the description of the snapshot of an n-object spatial scene of interest; the roles split into m+n immediate-successor (accessibility) relations, which are serial, irreflexive and antisymmetric, and of which m are general, not necessarily functional, the other n functional; the concrete domain Dx is generated by an RCC8-like spatial Relation Algebra (RA) x, and is used to guide the change by imposing spatial constraints on objects of the "followed" spatial scene, eventually at different time points of the input trees. In order to capture the expressiveness of most modal temporal logics encountered in the literature, we introduce weakly cyclic Terminological Boxes (TBoxes) of MTALC(Dx), whose axioms capture the decreasing property of modal temporal operators. We show the important result that satisfiability of an MTALC(Dx) concept with respect to a weakly cyclic TBox can be reduced to the emptiness problem of a Buchi weak alternating automaton augmented with spatial constraints. In another work, complementary to this one, also submitted to this conference, we thoroughly investigate Buchi automata augmented with spatial constraints, and provide, in particular, a translation of an alternating into a nondeterministic, and an effective decision procedure for the emptiness problem of the latter.