On coarser interval temporal logics

uncategorised

Authors

Emilio Muñoz Velasco

Mercedes Pelegrín

Pietro Sala

Guido Sciavicco

Ionel Eduard Stan

Published

1 January 2019

Publication details

Artificial Intelligence vol. 266 , pages 1-26.

Links

Abstract

The primary characteristic of interval temporal logic is that intervals, rather than points, are taken as the primitive ontological entities. Given their generally bad computational behavior of interval temporal logics, several techniques exist to produce decidable and computationally affordable temporal logics based on intervals. In this paper we take inspiration from Golumbic and Shamir’s coarser interval algebras, which generalize the classical Allen’s Interval Algebra, in order to define two previously unknown variants of Halpern and Shoham’s logic (HS) based on coarser relations. We prove that, perhaps surprisingly, the satisfiability problem for the coarsest of the two variants, namely HS3, not only is decidable, but PSpace-complete in the finite/discrete case, and PSpace-hard in any other case; besides proving its complexity bounds, we implement a tableau-based satisfiability checker for it and test it against a systematically generated benchmark. Our results are strengthened by showing that not all coarser-than-Allen’s relations are a guarantee of decidability, as we prove that the second variant, namely HS7, remains undecidable in all interesting cases.

Citation

Please, cite this work as:

[Mun+19] E. Mu~noz-Velasco, M. Pelegrín, P. Sala, et al. “On coarser interval temporal logics”. In: Artificial Intelligence 266 (2019), pp. 1-26. ISSN: 0004-3702. DOI: https://doi.org/10.1016/j.artint.2018.09.001. URL: https://www.sciencedirect.com/science/article/pii/S0004370218305964.

BibTeX

@Article{MUNOZVELASCO20191,
     title = {On coarser interval temporal logics},
     journal = {Artificial Intelligence},
     volume = {266},
     pages = {1-26},
     year = {2019},
     issn = {0004-3702},
     doi = {https://doi.org/10.1016/j.artint.2018.09.001},
     url = {https://www.sciencedirect.com/science/article/pii/S0004370218305964},
     author = {Emilio Mu{~n}oz-Velasco and Mercedes Pelegr{’}n and Pietro Sala and Guido Sciavicco and Ionel Eduard Stan},
     keywords = {Modal and temporal logic, (Un)Decidability, Complexity},
     abstract = {The primary characteristic of interval temporal logic is that intervals, rather than points, are taken as the primitive ontological entities. Given their generally bad computational behavior of interval temporal logics, several techniques exist to produce decidable and computationally affordable temporal logics based on intervals. In this paper we take inspiration from Golumbic and Shamir’s coarser interval algebras, which generalize the classical Allen’s Interval Algebra, in order to define two previously unknown variants of Halpern and Shoham’s logic (HS) based on coarser relations. We prove that, perhaps surprisingly, the satisfiability problem for the coarsest of the two variants, namely HS3, not only is decidable, but PSpace-complete in the finite/discrete case, and PSpace-hard in any other case; besides proving its complexity bounds, we implement a tableau-based satisfiability checker for it and test it against a systematically generated benchmark. Our results are strengthened by showing that not all coarser-than-Allen’s relations are a guarantee of decidability, as we prove that the second variant, namely HS7, remains undecidable in all interesting cases.},
}

Bibliometric data

The following data has been extracted from resources such as OpenAlex, Dimensions, PlumX or Altmetric.

Citations
CrossRef - Citation Indexes: 6
Scopus - Citation Indexes: 12

Captures
Mendeley - Readers: 17

Cites

The following graph plots the number of cites received by this work from its publication, on a yearly basis.

Papers citing this work

The following is a non-exhaustive list of papers that cite this work:

[1] H. Cheng, P. Li, R. Wang, et al. “Dynamic spatio‐temporal logic based on RCC‐8”. In: Concurrency and Computation: Practice and Experience 33.22 (Jul. 2020). ISSN: 1532-0634. DOI: 10.1002/cpe.5900. URL: http://dx.doi.org/10.1002/cpe.5900.

[2] W. Conradie, D. Della Monica, E. Muñoz-Velasco, et al. “Fuzzy Halpern and Shoham’s interval temporal logics”. In: Fuzzy Sets and Systems 456 (Mar. 2023), p. 107–124. ISSN: 0165-0114. DOI: 10.1016/j.fss.2022.05.014. URL: http://dx.doi.org/10.1016/j.fss.2022.05.014.

[3] G. Pagliarini, S. Scaboro, G. Serra, et al. “Neural-symbolic temporal decision trees for multivariate time series classification”. In: Information and Computation 301 (Dec. 2024), p. 105209. ISSN: 0890-5401. DOI: 10.1016/j.ic.2024.105209. URL: http://dx.doi.org/10.1016/j.ic.2024.105209.

[4] G. Pagliarini and G. Sciavicco. “Decision Tree Learning with Spatial Modal Logics”. In: Electronic Proceedings in Theoretical Computer Science 346 (Sep. 2021), p. 273–290. ISSN: 2075-2180. DOI: 10.4204/eptcs.346.18. URL: http://dx.doi.org/10.4204/eptcs.346.18.

[5] G. Pagliarini and G. Sciavicco. “Interpretable land cover classification with modal decision trees”. In: European Journal of Remote Sensing 56.1 (Dec. 2023). ISSN: 2279-7254. DOI: 10.1080/22797254.2023.2262738. URL: http://dx.doi.org/10.1080/22797254.2023.2262738.

[6] M. Sioutis, A. Paparrizou, and T. Janhunen. “On neighbourhood singleton-style consistencies for qualitative spatial and temporal reasoning”. In: Information and Computation 280 (Oct. 2021), p. 104638. ISSN: 0890-5401. DOI: 10.1016/j.ic.2020.104638. URL: http://dx.doi.org/10.1016/j.ic.2020.104638.

[7] M. Sioutis and D. Wolter. “Dynamic branching in qualitative constraint-based reasoning via counting local models”. In: Information and Computation 281 (Dec. 2021), p. 104787. ISSN: 0890-5401. DOI: 10.1016/j.ic.2021.104787. URL: http://dx.doi.org/10.1016/j.ic.2021.104787.

[8] C. Willem, D. M. Dario, M. Emilio, et al. “An Approach to Fuzzy Modal Logic of Time Intervals”. In: ECAI 2020. IOS Press, 2020. DOI: 10.3233/faia200156. URL: http://dx.doi.org/10.3233/faia200156.