Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2604.16488 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917417543794688 |
|---|---|
| author | Gasquet, Olivier |
| author_facet | Gasquet, Olivier |
| contents | Exact tight bounds of the complexity of the satisfiability problem for dense modal logics is a difficult question, likely somewhere between $\PSPACE$ and $\EXPSPACE$ depending of the logic under question. For a class of them, called here $n$-dense logics (characterized by axioms $\Box^n p\rightarrow \Box p$), we refine the known results -- membership in $\NEXPTIME$ -- in the light of parameterized complexity, as introduced in \cite{Downey}, and prove that they belong to the parameterized class para-$\PSPACE$: there exists a poly-space algorithm once the modal depth of the input is considered as a parameter. This is done by generalizing the novel analysis tool introduced in \cite{BalGasq25}, and therein called windows, to \emph{recursive windows}. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_16488 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Parameterized complexity of n-dense modal logics Gasquet, Olivier Logic in Computer Science Exact tight bounds of the complexity of the satisfiability problem for dense modal logics is a difficult question, likely somewhere between $\PSPACE$ and $\EXPSPACE$ depending of the logic under question. For a class of them, called here $n$-dense logics (characterized by axioms $\Box^n p\rightarrow \Box p$), we refine the known results -- membership in $\NEXPTIME$ -- in the light of parameterized complexity, as introduced in \cite{Downey}, and prove that they belong to the parameterized class para-$\PSPACE$: there exists a poly-space algorithm once the modal depth of the input is considered as a parameter. This is done by generalizing the novel analysis tool introduced in \cite{BalGasq25}, and therein called windows, to \emph{recursive windows}. |
| title | Parameterized complexity of n-dense modal logics |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2604.16488 |