License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2018.12
URN: urn:nbn:de:0030-drops-97779
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9777/
Go to the corresponding LIPIcs Volume Portal

Gavanelli, Marco ; Passantino, Alessandro ; Sciavicco, Guido

Deciding the Consistency of Branching Time Interval Networks

pdf-format:
LIPIcs-TIME-2018-12.pdf (0.4 MB)

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 tree-like partial order. While the problem of deciding the consistency of a network of IA-constraints is well-studied, 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 BA-relation, and, then, we prove that the consistency of a network of convex BA-relations can be decided via path consistency, and is therefore a polynomial problem. This is the first non-trivial 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:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-089-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{120},
  editor =	{Natasha Alechina and Kjetil N{\o}rv{\aa}g and Wojciech Penczek},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9777},
  URN =		{urn:nbn:de:0030-drops-97779},
  doi =		{10.4230/LIPIcs.TIME.2018.12},
  annote =	{Keywords: Constraint programming, Consistency, Branching time}
}

Keywords: Constraint programming, Consistency, Branching time
Collection: 25th International Symposium on Temporal Representation and Reasoning (TIME 2018)
Issue Date: 2018
Date of publication: 08.10.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI