6 papers
Parameterized complexity of n-dense modal logics
Olivier Gasquet
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 t…
FMP for QD logics. A wrong proof
Olivier Gasquet
This paper initially aimed at proposing a proof that quasi-dense logics have f.m.p, but it contains a major flaw, unfixable.
Recursive windows for grammar logics of bounded density
Olivier Gasquet
We introduce the family of multi-modal logics of bounded density and with a tableau-like approach using finite \emph{windows} which were introduced in \cite{BalGasq25} and that we…
Reopening of the conjecture about the decidability of Quasi-Dense Modal Logics (Comments on Lyon & Ostropolski-Nalewaja's result)
Olivier Gasquet
In \cite{Lyon24} the question of the decidability of quasi-dense modal logics is answered, and an upper bound in $\EXPSPACE$ is given. Unfortunately, authors' intricate proof seems…
PSPACE-completeness of bimodal transitive weak-density logic
Philippe Balbiani, Olivier Gasquet
Windows have been introduce in \cite{BalGasq25} as a tool for designing polynomial algorithms to check satisfiability of a bimodal logic of weak-density. In this paper, after revis…
Complexity of some modal logics of density (extended version)
Philippe Balbiani, Olivier Gasquet
By using a selective filtration argument, we prove that the satisfiability problem of the unimodal logic of density is in . By using a tableau-like approach, we prove that…