License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-24884
URL:

; ; ;

Decidability of the Interval Temporal Logic ABB over the Natural Numbers

pdf-format:


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 =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2488},
  annote =	{Keywords: Interval temporal logics, compass structures, decidability, complexity}
}

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


DROPS-Home | Fulltext Search | Imprint Published by LZI