License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2010.2488
URN: urn:nbn:de:0030-drops-24884
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2488/
Go to the corresponding LIPIcs Volume Portal

Montanari, Angelo ; Puppis, Gabriele ; Sala, Pietro ; Sciavicco, Guido

Decidability of the Interval Temporal Logic ABB over the Natural Numbers

pdf-format:
1001.MonatanariAngelo.2488.pdf (0.3 MB)

Abstract

In this paper, we focus our attention on the interval temporal logic
of the Allen's relations ``meets'', ``begins'', and ``begun by'' ($\ABB$ for short), interpreted over natural numbers. We first introduce the logic and we show that it is expressive enough to model distinctive interval properties, such as accomplishment conditions, to capture basic modalities of point-based temporal logic, such as the until operator, and to encode relevant metric constraints. Then, we prove that the satisfiability problem for $\ABB$ over natural numbers is decidable by providing a small model theorem based on an
original contraction method. Finally, we prove the EXPSPACE-completeness of the problem.

BibTeX - Entry

@InProceedings{montanari_et_al:LIPIcs:2010:2488,
  author =	{Angelo Montanari and Gabriele Puppis and Pietro Sala and Guido Sciavicco},
  title =	{{Decidability of the Interval Temporal Logic ABB over the Natural Numbers}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{597--608},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Jean-Yves Marion and Thomas Schwentick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2488},
  URN =		{urn:nbn:de:0030-drops-24884},
  doi =		{10.4230/LIPIcs.STACS.2010.2488},
  annote =	{Keywords: Interval temporal logics, compass structures, decidability, complexity}
}

Keywords: Interval temporal logics, compass structures, decidability, complexity
Collection: 27th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2010
Date of publication: 09.03.2010

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