Geodesic
Algorithmical properties of quasinormal modal logics with linear finite model property
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2018), pp. 87-97

Voir la notice de l'article provenant de la source Math-Net.Ru

We investigate the relationship between the complexity of a propositional modal logic and the complexity of models refuting the formulas not belonging to the logic. It is well-known that for many normal monomodal propositional logics the same constructions are used to establish both the PSPACE-completeness of a logic and the exponential lower-bound for the number of worlds in Kripke models refuting formulas not belonging to the logic. The same holds true for superintuitionistic propositional logics. As far as we know, there are no known mathematical criteria capturing this connection. In this paper, we show that if we discard the normality condition, and thus consider non-normal modal logics, we can construct quasi-normal logics with a linear model property whose complexity problem can be arbitrarily high. Moreover, this holds true if we only consider variable-free fragments of such logics.
Mots-clés : quasinormal modal logic
Keywords: computational complexity, decidability, Kripke semantics. 
@article{VTPMK_2018_4_a6,
     author = {M. N. Rybakov},
     title = {Algorithmical properties of quasinormal modal logics with linear finite model property},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {87--97},
     publisher = {mathdoc},
     number = {4},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2018_4_a6/}
}
TY  - JOUR
AU  - M. N. Rybakov
TI  - Algorithmical properties of quasinormal modal logics with linear finite model property
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2018
SP  - 87
EP  - 97
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2018_4_a6/
LA  - ru
ID  - VTPMK_2018_4_a6
ER  - 
%0 Journal Article
%A M. N. Rybakov
%T Algorithmical properties of quasinormal modal logics with linear finite model property
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2018
%P 87-97
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VTPMK_2018_4_a6/
%G ru
%F VTPMK_2018_4_a6
M. N. Rybakov. Algorithmical properties of quasinormal modal logics with linear finite model property. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 4 (2018), pp. 87-97. http://geodesic.mathdoc.fr/item/VTPMK_2018_4_a6/