Document Open Access Logo

On Expressiveness of Halpern-Shoham Logic and its Horn Fragments

Author Przemyslaw Andrzej Walega

PDF
Thumbnail PDF

File

LIPIcs.TIME.2017.22.pdf
  • Filesize: 0.61 MB
  • 18 pages

Document Identifiers

Author Details

Przemyslaw Andrzej Walega

Cite As Get BibTex

Przemyslaw Andrzej Walega. On Expressiveness of Halpern-Shoham Logic and its Horn Fragments. In 24th International Symposium on Temporal Representation and Reasoning (TIME 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 90, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.TIME.2017.22

Abstract

Abstract: Halpern and Shoham's modal logic of time intervals (HS in short) is an elegant and highly influential propositional interval-based logic. Its Horn fragments and their hybrid extensions have been recently intensively 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. We (1) show what time structures are definable in the language of HS, and (2) determine which HS fragments are capable of expressing: hybrid machinery, i.e., nominals and satisfaction operators, and somewhere, difference, and everywhere modal operators. These results enable us to classify HS Horn fragments according to their expressive power and to gain insight in the interplay between their decidability/computational complexity and expressiveness.

Subject Classification

Keywords
  • Temporal Logic
  • Interval Logic
  • Expressiveness
  • Hybrid Logic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. James F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11):832-843, 1983. Google Scholar
  2. Carlos Areces, Patrick Blackburn, and Maarten Marx. The computational complexity of hybrid temporal logics. Logic Journal of IGPL, 8(5):653-679, 2000. Google Scholar
  3. Alessandro Artale, Roman Kontchakov, Vladislav Ryzhikov, and Michael Zakharyaschev. Tractable interval temporal propo-sitional and description logics. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI-15), pages 1417-1423. 2015. Google Scholar
  4. Patrick Blackburn, Maarten De Rijke, and Yde Venema. Modal Logic, volume 53. Cambridge University Press, 2002. Google Scholar
  5. Sebastian Brandt, E. Güzel Kalaycı, Roman Kontchakov, Vladislav Ryzhikov, Guohui Xiao, and Michael Zakharyaschev. Ontology-based data access with a horn fragment of metric temporal logic. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pages 1070-1076, 2017. Google Scholar
  6. Davide Bresolin, Dario Della Monica, Angelo Montanari, Pietro Sala, and Guido Sciavicco. Interval temporal logics over strongly discrete linear orders: Expressiveness and complexity. Theoretical Computer Science, 560:269-291, 2014. Google Scholar
  7. Davide Bresolin, Dario Della Monica, Angelo Montanari, Pietro Sala, and Guido Sciavicco. The light side of interval temporal logic: The Bernays-Schönfinkel’s fragment of CDT. Annals of Mathematics and Artificial Intelligence, 71:11-39, 2014. Google Scholar
  8. Davide Bresolin, Agi Kurucz, Emilio Muñoz-Velasco, Vladislav Ryzhikov, Guido Sciavicco, and Michael Zakharyaschev. Horn fragments of the Halpern-Shoham interval temporal logic, Forthcoming. URL: https://arxiv.org/pdf/1604.03515v1.pdf.
  9. Davide Bresolin, Emilio Muñoz-Velasco, and Guido Sciavicco. Sub-propositional fragments of the interval temporal logic of Allen’s relations. In European Workshop on Logics in Artificial Intelligence, pages 122-136. Springer, 2014. Google Scholar
  10. Davide Bresolin, Emilio Munoz-Velasco, and Guido Sciavicco. On the complexity of fragments of horn modal logics. In Temporal Representation and Reasoning (TIME), 2016 23rd International Symposium on, pages 186-195. IEEE, 2016. Google Scholar
  11. Dario Della Monica, Valentin Goranko, Angelo Montanari, Guido Sciavicco, et al. Interval temporal logics: a journey. Bulletin of EATCS, 3(105), 2013. Google Scholar
  12. Valentin Goranko, Angelo Montanari, and Guido Sciavicco. A road map of interval temporal logics and duration calculi. Journal of Applied Non-Classical Logics, 14(1-2):9-54, 2004. Google Scholar
  13. Joseph Y. Halpern and Yoav Shoham. A propositional modal logic of time intervals. Journal of the ACM (JACM), 38(4):935-962, 1991. Google Scholar
  14. Roman Kontchakov, Laura Pandolfo, Luca Pulina, Vladislav Ryzhikov, and Michael Zakharyaschev. Temporal and spatial OBDA with many-dimensional Halpern-Shoham logic. In IJCAI, pages 1160-1166, 2016. Google Scholar
  15. Angelo Montanari, Ian Pratt-Hartmann, and Pietro Sala. Decidability of the logics of the reflexive sub-interval and super-interval relations over finite linear orders. In Temporal Representation and Reasoning (TIME), 2010 17th International Symposium on, pages 27-34. IEEE, 2010. Google Scholar
  16. Yde Venema. Expressiveness and completeness of an interval tense logic. Notre Dame journal of formal logic, 31(4):529-547, 1990. Google Scholar
  17. Przemysław A. Wałęga. Computational complexity of a hybridized Horn fragment of Halpern-Shoham logic. In Indian Conference on Logic and Its Applications, pages 224-238. Springer, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact