2026-08-17T10:27:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2488 2024-03-06T10:33:26Z ddc:004 open_access

Decidability of the Interval Temporal Logic ABB over the Natural Numbers Montanari, Angelo Puppis, Gabriele Sala, Pietro Sciavicco, Guido Interval temporal logics compass structures decidability complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Angelo Montanari and Gabriele Puppis and Pietro Sala and Guido Sciavicco 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2488 urn:nbn:de:0030-drops-24884 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2488 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode