Logics with the axiom of convergence: complexity with a small number of variables in the language (extended version)
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908556304842752 |
|---|---|
| author | Rybakov, M. Shcherbakov, M. |
| author_facet | Rybakov, M. Shcherbakov, M. |
| contents | It is known that many modal and superintuitionistic logics are PSPACE-hard in languages with a small number of variables; however, questions about the complexity of similar fragments of many logics obtained by adding various axioms to "standard" ones remain unexplored. We investigate the complexity of fragments of modal logics obtained by adding an axiom requiring the convergence of the accessibility relation in Kripke frames: S4.2, K4.2, Grz.2, and GL.2. The main result is that S4.2 and Grz.2 are PSPACE-complete in a language with two variables, while K4.2 and GL.2* (a logic near to GL.2) are PSPACE-complete in a language with one variable. The obtained results are extended to infinite classes of logics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_12343 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Logics with the axiom of convergence: complexity with a small number of variables in the language (extended version) Rybakov, M. Shcherbakov, M. Logic It is known that many modal and superintuitionistic logics are PSPACE-hard in languages with a small number of variables; however, questions about the complexity of similar fragments of many logics obtained by adding various axioms to "standard" ones remain unexplored. We investigate the complexity of fragments of modal logics obtained by adding an axiom requiring the convergence of the accessibility relation in Kripke frames: S4.2, K4.2, Grz.2, and GL.2. The main result is that S4.2 and Grz.2 are PSPACE-complete in a language with two variables, while K4.2 and GL.2* (a logic near to GL.2) are PSPACE-complete in a language with one variable. The obtained results are extended to infinite classes of logics. |
| title | Logics with the axiom of convergence: complexity with a small number of variables in the language (extended version) |
| topic | Logic |
| url | https://arxiv.org/abs/2507.12343 |