Horn Fragments of the Halpern-Shoham Interval Temporal Logic

 

Abstract

We investigate the satisfiability problem for Horn fragments of the Halpern-Shoham interval temporal logic depending on the type (box or diamond) of the interval modal operators, the type of the underlying linear order (discrete or dense), and the type of semantics for the interval relations (reflexive or irreflexive). For example, we show that satisfiability of Horn formulas with diamonds is undecidable for any type of linear orders and semantics. On the contrary, satisfiability of Horn formulas with boxes is tractable over both discrete and dense orders under the reflexive semantics and over dense orders under the irreflexive semantics but becomes undecidable over discrete orders under the irreflexive semantics. Satisfiability of binary Horn formulas with both boxes and diamonds is always undecidable under the irreflexive semantics.

Citation

Please, cite this work as:

[Bre+17] D. Bresolin, A. Kurucz, E. Mu~noz-Velasco, et al. “Horn Fragments of the Halpern-Shoham Interval Temporal Logic”. In: ACM Trans. Comput. Log. 18.3 (2017), pp. 22:1-22:39. DOI: 10.1145/3105909. URL: https://doi.org/10.1145/3105909.

NoteBibTeX

@Article{Bresolin2017,
     author = {Davide Bresolin and Agi Kurucz and Emilio Mu~noz-Velasco and Vladislav Ryzhikov and Guido Sciavicco and Michael Zakharyaschev},
     journal = {{ACM} Trans. Comput. Log.},
     title = {Horn Fragments of the Halpern-Shoham Interval Temporal Logic},
     year = {2017},
     number = {3},
     pages = {22:1–22:39},
     volume = {18},
     bibsource = {dblp computer science bibliography, https://dblp.org},
     biburl = {https://dblp.org/rec/journals/tocl/BresolinKMRSZ17.bib},
     doi = {10.1145/3105909},
     timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
     url = {https://doi.org/10.1145/3105909},
}

Bibliometric data

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

Horn Fragments of the Halpern-Shoham Interval Temporal Logic

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] S. Brandt, E. Güzel Kalaycı, R. Kontchakov, et al. “Ontology-Based Data Access with a Horn Fragment of Metric Temporal Logic”. In: Proceedings of the AAAI Conference on Artificial Intelligence 31.1 (Feb. 2017). ISSN: 2159-5399. DOI: 10.1609/aaai.v31i1.10696. URL: http://dx.doi.org/10.1609/aaai.v31i1.10696.

[2] S. Brandt, E. G. Kalaycı, V. Ryzhikov, et al. “Querying Log Data with Metric Temporal Logic”. In: Journal of Artificial Intelligence Research 62 (Aug. 2018), p. 829–877. ISSN: 1076-9757. DOI: 10.1613/jair.1.11229. URL: http://dx.doi.org/10.1613/jair.1.11229.

[3] D. Bresolin, A. Kurucz, E. Muñoz-Velasco, et al. “Horn Fragments of the Halpern-Shoham Interval Temporal Logic”. In: ACM Transactions on Computational Logic 18.3 (Jul. 2017), p. 1–39. ISSN: 1557-945X. DOI: 10.1145/3105909. URL: http://dx.doi.org/10.1145/3105909.

[4] D. Bresolin, E. Muñoz-Velasco, and G. Sciavicco. “On Sub-Propositional Fragments of Modal Logic”. In: Logical Methods in Computer Science Volume 14, Issue 2 (Jun. 2018). ISSN: 1860-5974. DOI: 10.23638/lmcs-14(2:16)2018. URL: http://dx.doi.org/10.23638/lmcs-14(2:16)2018.

[5] D. Bresolin, E. Muñoz-Velasco, and G. Sciavicco. “On the Complexity of Fragments of Horn Modal Logics”. In: 2016 23rd International Symposium on Temporal Representation and Reasoning (TIME). IEEE, Oct. 2016, p. 186–195. DOI: 10.1109/time.2016.27. URL: http://dx.doi.org/10.1109/time.2016.27.

[6] D. Bresolin, E. Muñoz-Velasco, and G. Sciavicco. “On the Expressive Power of Sub-Propositional Fragments of Modal Logic”. In: Electronic Proceedings in Theoretical Computer Science 226 (Sep. 2016), p. 91–104. ISSN: 2075-2180. DOI: 10.4204/eptcs.226.7. URL: http://dx.doi.org/10.4204/eptcs.226.7.

[7] 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.

[8] E. Muñoz-Velasco, M. Pelegrín, P. Sala, et al. “On coarser interval temporal logics”. In: Artificial Intelligence 266 (Jan. 2019), p. 1–26. ISSN: 0004-3702. DOI: 10.1016/j.artint.2018.09.001. URL: http://dx.doi.org/10.1016/j.artint.2018.09.001.

[9] 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.

[10] 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.

[11] 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.

[12] T. Schneider and M. Šimkus. “Ontologies and Data Management: A Brief Survey”. In: KI - Künstliche Intelligenz 34.3 (Aug. 2020), p. 329–353. ISSN: 1610-1987. DOI: 10.1007/s13218-020-00686-3. URL: http://dx.doi.org/10.1007/s13218-020-00686-3.

[13] G. Sciavicco, I. E. Stan, and A. Vaccari. “Towards a General Method for Logical Rule Extraction from Time Series”. In: From Bioinspired Systems and Biomedical Applications to Machine Learning. Springer International Publishing, 2019, p. 3–12. ISBN: 9783030196516. DOI: 10.1007/978-3-030-19651-6_1. URL: http://dx.doi.org/10.1007/978-3-030-19651-6_1.

[14] P. A. Wałęga. “Computational Complexity of a Hybridized Horn Fragment of Halpern-Shoham Logic”. In: Logic and Its Applications. Springer Berlin Heidelberg, Dec. 2016, p. 224–238. ISBN: 9783662540695. DOI: 10.1007/978-3-662-54069-5_17. URL: http://dx.doi.org/10.1007/978-3-662-54069-5_17.

[15] P. A. Wałęga. “Computational Complexity of Core Fragments of Modal Logics T, K4, and S4”. In: Logics in Artificial Intelligence. Springer International Publishing, 2019, p. 744–759. ISBN: 9783030195700. DOI: 10.1007/978-3-030-19570-0_48. URL: http://dx.doi.org/10.1007/978-3-030-19570-0_48.

[16] P. A. Wałęga. “Computational complexity of hybrid interval temporal logics”. In: Annals of Pure and Applied Logic 174.1 (Jan. 2023), p. 103165. ISSN: 0168-0072. DOI: 10.1016/j.apal.2022.103165. URL: http://dx.doi.org/10.1016/j.apal.2022.103165.

[17] P. A. Wałęga. “Hybrid fragments of Halpern–Shoham logic and their expressive power”. In: Theoretical Computer Science 797 (Dec. 2019), p. 102–128. ISSN: 0304-3975. DOI: 10.1016/j.tcs.2019.01.014. URL: http://dx.doi.org/10.1016/j.tcs.2019.01.014.

[18] P. A. Wałęga. “Searching for Well-Behaved Fragments of Halpern-Shoham Logic”. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. IJCAI-2017. International Joint Conferences on Artificial Intelligence Organization, Aug. 2017, p. 5219–5220. DOI: 10.24963/ijcai.2017/769. URL: http://dx.doi.org/10.24963/ijcai.2017/769.

[19] 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.