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〉).

Pspace-completeness of the temporal logic of sub-intervals and suffixes / Bozzelli, L.; Montanari, A.; Peron, A.; Sala, P.. - 206:(2021), pp. 1-19. (Intervento presentato al convegno 28th International Symposium on Temporal Representation and Reasoning, TIME 2021 tenutosi a aut nel 2021) [10.4230/LIPIcs.TIME.2021.9].

Pspace-completeness of the temporal logic of sub-intervals and suffixes

Bozzelli L.;Montanari A.;Peron A.;
2021

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〉).
2021
Pspace-completeness of the temporal logic of sub-intervals and suffixes / Bozzelli, L.; Montanari, A.; Peron, A.; Sala, P.. - 206:(2021), pp. 1-19. (Intervento presentato al convegno 28th International Symposium on Temporal Representation and Reasoning, TIME 2021 tenutosi a aut nel 2021) [10.4230/LIPIcs.TIME.2021.9].
File in questo prodotto:
File Dimensione Formato  
LIPIcs-TIME-2021-9.pdf

accesso aperto

Descrizione: Articolo principale
Tipologia: Versione Editoriale (PDF)
Licenza: Dominio pubblico
Dimensione 797.68 kB
Formato Adobe PDF
797.68 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/884683
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact