License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2021.9
URN: urn:nbn:de:0030-drops-147853
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14785/
Go to the corresponding LIPIcs Volume Portal

Bozzelli, Laura ; Montanari, Angelo ; Peron, Adriano ; Sala, Pietro

Pspace-Completeness of the Temporal Logic of Sub-Intervals and Suffixes

pdf-format:
LIPIcs-TIME-2021-9.pdf (0.8 MB)

Abstract

In this paper, we establish Pspace-completeness of the finite satisfiability and model checking problems for the fragment of Halpern and Shoham interval logic with modality ⟨E⟩, for the "suffix" relation on pairs of intervals, and modality ⟨D⟩, for the "sub-interval" relation, under the homogeneity assumption. The result significantly improves the Expspace upper bound recently established for the same fragment, and proves the rather surprising fact that the complexity of the considered problems does not change when we add either the modality for suffixes (⟨E⟩) or, symmetrically, the modality for prefixes (⟨B⟩) to the logic of sub-intervals (featuring only ⟨D⟩).

BibTeX - Entry

@InProceedings{bozzelli_et_al:LIPIcs.TIME.2021.9,
  author =	{Bozzelli, Laura and Montanari, Angelo and Peron, Adriano and Sala, Pietro},
  title =	{{Pspace-Completeness of the Temporal Logic of Sub-Intervals and Suffixes}},
  booktitle =	{28th International Symposium on Temporal Representation and Reasoning (TIME 2021)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-206-8},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{206},
  editor =	{Combi, Carlo and Eder, Johann and Reynolds, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14785},
  URN =		{urn:nbn:de:0030-drops-147853},
  doi =		{10.4230/LIPIcs.TIME.2021.9},
  annote =	{Keywords: Interval temporal logic, Satisfiability, Model checking}
}

Keywords: Interval temporal logic, Satisfiability, Model checking
Collection: 28th International Symposium on Temporal Representation and Reasoning (TIME 2021)
Issue Date: 2021
Date of publication: 16.09.2021

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