On the Expressive Power of Sub-Propositional Fragments of Modal Logic
Modal logic is a paradigm for several useful and applicable formal systems in computer science. It generally retains the low complexity of classical propositional logic, but notable exceptions exist in the domains of description, temporal, and spatial logic, where the most expressive formalisms have...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2016-09-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1609.04091v1 |
| _version_ | 1818588654595997696 |
|---|---|
| author | Davide Bresolin Emilio Muñoz-Velasco Guido Sciavicco |
| author_facet | Davide Bresolin Emilio Muñoz-Velasco Guido Sciavicco |
| author_sort | Davide Bresolin |
| collection | DOAJ |
| description | Modal logic is a paradigm for several useful and applicable formal systems in computer science. It generally retains the low complexity of classical propositional logic, but notable exceptions exist in the domains of description, temporal, and spatial logic, where the most expressive formalisms have a very high complexity or are even undecidable. In search of computationally well-behaved fragments, clausal forms and other sub-propositional restrictions of temporal and description logics have been recently studied. This renewed interest on sub-propositional logics, which mainly focus on the complexity of the various fragments, raise natural questions on their the relative expressive power, which we try to answer here for the basic multi-modal logic Kn. We consider the Horn and the Krom restrictions, as well as the combined restriction (known as the core fragment) of modal logic, and, orthogonally, the fragments that emerge by disallowing boxes or diamonds from positive literals. We study the problem in a very general setting, to ease transferring our results to other meaningful cases. |
| first_indexed | 2024-12-16T09:28:08Z |
| format | Article |
| id | doaj.art-9129204a7cd342b2b387066408237bdc |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-16T09:28:08Z |
| publishDate | 2016-09-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-9129204a7cd342b2b387066408237bdc2022-12-21T22:36:37ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802016-09-01226Proc. GandALF 20169110410.4204/EPTCS.226.7:4On the Expressive Power of Sub-Propositional Fragments of Modal LogicDavide Bresolin0Emilio Muñoz-Velasco1Guido Sciavicco2 University of Bologna University of Malaga University of Ferrara Modal logic is a paradigm for several useful and applicable formal systems in computer science. It generally retains the low complexity of classical propositional logic, but notable exceptions exist in the domains of description, temporal, and spatial logic, where the most expressive formalisms have a very high complexity or are even undecidable. In search of computationally well-behaved fragments, clausal forms and other sub-propositional restrictions of temporal and description logics have been recently studied. This renewed interest on sub-propositional logics, which mainly focus on the complexity of the various fragments, raise natural questions on their the relative expressive power, which we try to answer here for the basic multi-modal logic Kn. We consider the Horn and the Krom restrictions, as well as the combined restriction (known as the core fragment) of modal logic, and, orthogonally, the fragments that emerge by disallowing boxes or diamonds from positive literals. We study the problem in a very general setting, to ease transferring our results to other meaningful cases.http://arxiv.org/pdf/1609.04091v1 |
| spellingShingle | Davide Bresolin Emilio Muñoz-Velasco Guido Sciavicco On the Expressive Power of Sub-Propositional Fragments of Modal Logic Electronic Proceedings in Theoretical Computer Science |
| title | On the Expressive Power of Sub-Propositional Fragments of Modal Logic |
| title_full | On the Expressive Power of Sub-Propositional Fragments of Modal Logic |
| title_fullStr | On the Expressive Power of Sub-Propositional Fragments of Modal Logic |
| title_full_unstemmed | On the Expressive Power of Sub-Propositional Fragments of Modal Logic |
| title_short | On the Expressive Power of Sub-Propositional Fragments of Modal Logic |
| title_sort | on the expressive power of sub propositional fragments of modal logic |
| url | http://arxiv.org/pdf/1609.04091v1 |
| work_keys_str_mv | AT davidebresolin ontheexpressivepowerofsubpropositionalfragmentsofmodallogic AT emiliomunozvelasco ontheexpressivepowerofsubpropositionalfragmentsofmodallogic AT guidosciavicco ontheexpressivepowerofsubpropositionalfragmentsofmodallogic |