Modal Fragments
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911488507117568 |
|---|---|
| author | Bezhanishvili, Nick Cate, Balder ten Ganguly, Arunavo Meier, Arne |
| author_facet | Bezhanishvili, Nick Cate, Balder ten Ganguly, Arunavo Meier, Arne |
| contents | We survey systematic approaches to basis-restricted fragments of propositional logic and modal logics, with an emphasis on how expressive power and computational complexity depend on the allowed operators. The propositional case is well-established and serves as a conceptual template: Post's lattice organizes fragments via Boolean clones and supports complexity classifications for standard reasoning tasks. For modal fragments, we then bring together two historically independent lines of investigation: a general framework where modal fragments are parameterized by a basis of "connectives" defined by arbitrary modal formulas (initially proposed and studied by logicians such as Kuznetsov and Ratsa in the 1970s), and the more tractable class of what we call simple modal fragments parameterized by Boolean functions plus selected modal operators, where Post-lattice methods enable systematic decidability and dichotomy results. Along the way, we collect and extend results on teachability and exact learnability from examples for both propositional fragments and simple modal fragments, and we conclude by identifying several open problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05055 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Modal Fragments Bezhanishvili, Nick Cate, Balder ten Ganguly, Arunavo Meier, Arne Logic in Computer Science Logic We survey systematic approaches to basis-restricted fragments of propositional logic and modal logics, with an emphasis on how expressive power and computational complexity depend on the allowed operators. The propositional case is well-established and serves as a conceptual template: Post's lattice organizes fragments via Boolean clones and supports complexity classifications for standard reasoning tasks. For modal fragments, we then bring together two historically independent lines of investigation: a general framework where modal fragments are parameterized by a basis of "connectives" defined by arbitrary modal formulas (initially proposed and studied by logicians such as Kuznetsov and Ratsa in the 1970s), and the more tractable class of what we call simple modal fragments parameterized by Boolean functions plus selected modal operators, where Post-lattice methods enable systematic decidability and dichotomy results. Along the way, we collect and extend results on teachability and exact learnability from examples for both propositional fragments and simple modal fragments, and we conclude by identifying several open problems. |
| title | Modal Fragments |
| topic | Logic in Computer Science Logic |
| url | https://arxiv.org/abs/2603.05055 |