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.2020.5
URN: urn:nbn:de:0030-drops-129736
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12973/
Go to the corresponding LIPIcs Volume Portal

Bertagnon, Alessandro ; Gavanelli, Marco ; Passantino, Alessandro ; Sciavicco, Guido ; Trevisani, Stefano

The Horn Fragment of Branching Algebra

pdf-format:
LIPIcs-TIME-2020-5.pdf (0.5 MB)

Abstract

Branching Algebra is the natural branching-time generalization of Allen’s Interval Algebra. As in the linear case, the consistency problem for Branching Algebra is NP-hard. Being relatively new, however, not much is known about the computational behaviour of the consistency problem of its sub-algebras, except in the case of the recently found subset of convex branching relations, for which the consistency of a network can be tested via path consistency and it is therefore deterministic polynomial. In this paper, following Nebel and Bürckert, we define the Horn fragment of Branching Algebra, and prove that it is a sub-algebra of the latter, being closed under inverse, intersection, and composition, that it strictly contains both the convex fragment of Branching Algebra and the Horn fragment of Interval Algebra, and that its consistency problem can be decided via path consistency. Finally, we experimentally prove that the Horn fragment of Branching Algebra can be used as an heuristic for checking the consistency of a generic network with a considerable improvement over the convex subset.

BibTeX - Entry

@InProceedings{bertagnon_et_al:LIPIcs:2020:12973,
  author =	{Alessandro Bertagnon and Marco Gavanelli and Alessandro Passantino and Guido Sciavicco and Stefano Trevisani},
  title =	{{The Horn Fragment of Branching Algebra}},
  booktitle =	{27th International Symposium on Temporal Representation and Reasoning (TIME 2020)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-167-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{178},
  editor =	{Emilio Mu{\~n}oz-Velasco and Ana Ozaki and Martin Theobald},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12973},
  URN =		{urn:nbn:de:0030-drops-129736},
  doi =		{10.4230/LIPIcs.TIME.2020.5},
  annote =	{Keywords: Constraint programming, Consistency, Branching time, Horn Fragment}
}

Keywords: Constraint programming, Consistency, Branching time, Horn Fragment
Collection: 27th International Symposium on Temporal Representation and Reasoning (TIME 2020)
Issue Date: 2020
Date of publication: 15.09.2020

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