Hybrid fragments of Halpern-Shoham logic and their expressive power. (English) Zbl 1434.03068
Summary: Halpern and Shoham modal logic of time intervals \((\mathsf{HS}\) in short) is an elegant and highly influential propositional interval-based modal logic. Its sub-propositional fragments, that is fragments obtained by restricting use of propositional connectives, and their hybrid extensions with nominals and satisfaction operators have been recently studied and successfully applied in real-world use cases. Detailed investigation of their decidability and computational complexity has been conducted, however, there has been significantly less research on their expressive power. In this paper we make a step towards filling this gap. In particular, we (1) compare classes of frames definable in full \(\mathsf{HS}\) and in its hybrid extension, and (2) determine in which sub-propositional \(\mathsf{HS}\)-fragments we can express the difference operator, nominals, and satisfaction operators. The obtained results enable us to classify \(\mathsf{HS}\), its sub-propositional fragments, and their hybrid extensions according to their expressive power.
References:
| [1] | Halpern, J. Y.; Shoham, Y., A propositional modal logic of time intervals, J. ACM, 38, 4, 935-962 (1991) · Zbl 0799.68175 |
| [2] | Bresolin, D.; Muñoz-Velasco, E.; Sciavicco, G., Sub-propositional fragments of the interval temporal logic of Allen’s relations, (European Conference on Logics in Artificial Intelligence (2014), Springer), 122-136 · Zbl 1432.03028 |
| [3] | Bresolin, D.; Kurucz, A.; Muñoz-Velasco, E.; Ryzhikov, V.; Sciavicco, G.; Zakharyaschev, M., Horn fragments of the Halpern-Shoham interval temporal logic, ACM Trans. Comput. Log., 18, 3, 22:1-22:39 (2017) · Zbl 1407.03029 |
| [4] | Bresolin, D.; Muñoz-Velasco, E.; Sciavicco, G., Fast(er) reasoning in interval temporal logic, LIPIcs-Leibniz International Proceedings in Informatics, vol. 82 (2017), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik · Zbl 1434.03066 |
| [5] | Wałęga, P. A., Computational complexity of a hybridized Horn fragment of Halpern-Shoham logic, (Indian Conference on Logic and Its Applications (2017), Springer), 224-238 · Zbl 1485.03044 |
| [6] | Artale, A.; Kontchakov, R.; Ryzhikov, V.; Zakharyaschev, M., Tractable interval temporal propositional and description logics, (Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-15) (2015)), 1417-1423 |
| [7] | Kontchakov, R.; Pandolfo, L.; Pulina, L.; Ryzhikov, V.; Zakharyaschev, M., Temporal and spatial OBDA with many-dimensional Halpern-Shoham logic, (IJCAI (2016)), 1160-1166 |
| [8] | Allen, J. F., Maintaining knowledge about temporal intervals, Commun. ACM, 26, 11, 832-843 (1983) · Zbl 0519.68079 |
| [9] | D. Della Monica, V. Goranko, A. Montanari, G. Sciavicco, et al., Interval temporal logics: a journey, Bulletin of EATCS 3 (105). · Zbl 1275.03087 |
| [10] | Goranko, V.; Montanari, A.; Sciavicco, G., A road map of interval temporal logics and duration calculi, J. Appl. Non-Classical Logics, 14, 1-2, 9-54 (2004) · Zbl 1181.03012 |
| [11] | Bresolin, D.; Della Monica, D.; Montanari, A.; Sala, P.; Sciavicco, G., Interval temporal logics over strongly discrete linear orders: expressiveness and complexity, Theoret. Comput. Sci., 560, 269-291 (2014) · Zbl 1335.03017 |
| [12] | Montanari, A.; Pratt-Hartmann, I.; Sala, P., Decidability of the logics of the reflexive sub-interval and super-interval relations over finite linear orders, (2010 17th International Symposium on Temporal Representation and Reasoning (TIME) (2010), IEEE), 27-34 |
| [13] | Bresolin, D.; Della Monica, D.; Montanari, A.; Sala, P.; Sciavicco, G., The light side of interval temporal logic: the Bernays-Schönfinkel’s fragment of CDT, Ann. Math. Artif. Intell., 71, 11-39 (2014) · Zbl 1325.03015 |
| [14] | Bresolin, D.; Munoz-Velasco, E.; Sciavicco, G., On the complexity of fragments of Horn modal logics, (2016 23rd International Symposium on Temporal Representation and Reasoning (TIME) (2016), IEEE), 186-195 |
| [15] | Brandt, S.; Kalayci, E. G.; Kontchakov, R.; Ryzhikov, V.; Xiao, G.; Zakharyaschev, M., Ontology-based data access with a Horn fragment of metric temporal logic, (AAAI (2017)), 1070-1076 |
| [16] | Goranko, V.; Montanari, A.; Sciavicco, G., Propositional interval neighborhood temporal logics, J.UCS, 9, 9, 1137-1167 (2003) |
| [17] | Della Monica, D.; Goranko, V.; Montanari, A.; Sciavicco, G., Expressiveness of the interval logics of Allen’s relations on the class of all linear orders: complete classification, (IJCAI Proceedings-International Joint Conference on Artificial Intelligence, vol. 22 (2011)), 845 |
| [18] | Aceto, L.; Della Monica, D.; Ingólfsdóttir, A.; Montanari, A.; Sciavicco, G., A complete classification of the expressiveness of interval logics of Allen’s relations over dense linear orders, (2013 20th International Symposium on Temporal Representation and Reasoning (TIME) (2013)), 65-72 |
| [19] | Aceto, L.; Della Monica, D.; Ingólfsdóttir, A.; Montanari, A.; Sciavicco, G., On the expressiveness of the interval logic of Allen’s relations over finite and discrete linear orders, (European Workshop on Logics in Artificial Intelligence (2014), Springer), 267-281 · Zbl 1432.03027 |
| [20] | Venema, Y., Expressiveness and completeness of an interval tense logic, Notre Dame J. Form. Log., 31, 4, 529-547 (1990) · Zbl 0725.03006 |
| [21] | Bresolin, D.; Della Monica, D.; Montanari, A.; Sala, P.; Sciavicco, G., On the complexity of fragments of the modal logic of Allen’s relations over dense structures, (LATA (2015)), 511-523 · Zbl 1451.03020 |
| [22] | Fisher, M., A resolution method for temporal logic, (IJCAI, vol. 91 (1991)), 99-104 · Zbl 0745.68091 |
| [23] | Areces, C.; Blackburn, P.; Marx, M., The computational complexity of hybrid temporal logics, Log. J. IGPL, 8, 5, 653-679 (2000) · Zbl 0959.03011 |
| [24] | P. Blackburn, Representation, reasoning, and relational structures: a hybrid logic manifesto, Logic Journal of the IGPL 8 (3). · Zbl 0956.03025 |
| [25] | Blackburn, P.; De Rijke, M.; Venema, Y., Modal Logic, vol. 53 (2002), Cambridge University Press |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
