Gavanelli, Marco ;
Passantino, Alessandro ;
Sciavicco, Guido
Deciding the Consistency of Branching Time Interval Networks
Abstract
Allen's Interval Algebra (IA) is one of the most prominent formalisms in the area of qualitative temporal reasoning; however, its applications are naturally restricted to linear flows of time. When dealing with nonlinear time, Allen's algebra can be extended in several ways, and, as suggested by Ragni and Wölfl [M. Ragni and S. Wölfl, 2004], a possible solution consists in defining the Branching Algebra (BA) as a set of 19 basic relations (13 basic linear relations plus 6 new basic nonlinear ones) in such a way that each basic relation between two intervals is completely defined by the relative position of the endpoints on a treelike partial order. While the problem of deciding the consistency of a network of IAconstraints is wellstudied, and every subset of the IA has been classified with respect to the tractability of its consistency problem, the fragments of the BA have received less attention. In this paper, we first define the notion of convex BArelation, and, then, we prove that the consistency of a network of convex BArelations can be decided via path consistency, and is therefore a polynomial problem. This is the first nontrivial tractable fragment of the BA; given the clear parallel with the linear case, our contribution poses the bases for a deeper study of fragments of BA towards their complete classification.
BibTeX  Entry
@InProceedings{gavanelli_et_al:LIPIcs:2018:9777,
author = {Marco Gavanelli and Alessandro Passantino and Guido Sciavicco},
title = {{Deciding the Consistency of Branching Time Interval Networks}},
booktitle = {25th International Symposium on Temporal Representation and Reasoning (TIME 2018)},
pages = {12:112:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770897},
ISSN = {18688969},
year = {2018},
volume = {120},
editor = {Natasha Alechina and Kjetil N{\o}rv{\aa}g and Wojciech Penczek},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9777},
URN = {urn:nbn:de:0030drops97779},
doi = {10.4230/LIPIcs.TIME.2018.12},
annote = {Keywords: Constraint programming, Consistency, Branching time}
}
08.10.2018
Keywords: 

Constraint programming, Consistency, Branching time 
Seminar: 

25th International Symposium on Temporal Representation and Reasoning (TIME 2018)

Issue date: 

2018 
Date of publication: 

08.10.2018 