Hybrid fragments of Halpern–Shoham logic and their expressive power
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 satis...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2019
|
| _version_ | 1797062541058244608 |
|---|---|
| author | Wałęga, P |
| author_facet | Wałęga, P |
| author_sort | Wałęga, P |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T20:46:59Z |
| format | Journal article |
| id | oxford-uuid:363c4d44-aa70-4612-ab4b-c8290c4ef20f |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T20:46:59Z |
| publishDate | 2019 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:363c4d44-aa70-4612-ab4b-c8290c4ef20f2022-03-26T13:36:38ZHybrid fragments of Halpern–Shoham logic and their expressive powerJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:363c4d44-aa70-4612-ab4b-c8290c4ef20fEnglishSymplectic Elements at OxfordElsevier2019Wałęga, PHalpern 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. |
| spellingShingle | Wałęga, P Hybrid fragments of Halpern–Shoham logic and their expressive power |
| title | Hybrid fragments of Halpern–Shoham logic and their expressive power |
| title_full | Hybrid fragments of Halpern–Shoham logic and their expressive power |
| title_fullStr | Hybrid fragments of Halpern–Shoham logic and their expressive power |
| title_full_unstemmed | Hybrid fragments of Halpern–Shoham logic and their expressive power |
| title_short | Hybrid fragments of Halpern–Shoham logic and their expressive power |
| title_sort | hybrid fragments of halpern shoham logic and their expressive power |
| work_keys_str_mv | AT wałegap hybridfragmentsofhalpernshohamlogicandtheirexpressivepower |