Hybrid fragments of Halpern–Shoham logic and their expressive power

Journal article

Halpern and Shoham modal logic of time intervals ( 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 and in its hybrid extension, and (2) determine in which sub-propositional -fragments we can express the difference operator, nominals, and satisfaction operators. The obtained results enable us to classify , its sub-propositional fragments, and their hybrid extensions according to their expressive power.

Authors: Wałęga, P

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Theoretical Computer Science
• Volume: 797
• Pages: 102-128
• Publication date: 2019-01-17
• Acceptance date: 2019-01-08
• DOI: 10.1016/j.tcs.2019.01.014
• ISSN: 0304-3975
• Language: English
• Keywords: expressive power; FFR; interval logic; Halpern–Shoham logic; temporal logic; hybrid logic