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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2018},
     number = {4},
     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
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
%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/

[1] Zakharyashchev M. V., Popov S. V., On the power of countermodels of intuitionistic calculus, Preprint IPI AN SSSR, 1980 (in Russian)

[2] Kuznetsov A. V., “O sredstvakh obnaruzheniya nevyvodimosti ili nevyrazimosti”, Inference, Nauka Publ., Moscow, 1979, 5–33 (in Russian)

[3] Chagrov A. V., “O slozhnosti propozitsionalnykh logik”, The complexity problems of mathematical logic, KSU Publ., Kalinin, 1985, 80–90 (in Russian)

[4] Chagrov A., Zakharyaschev M., Modal Logic, Oxford University Press, Oxford, 1997 | MR | Zbl

[5] Kuznetsov A. V., “On Superintuitionistic Logics”, Proceedings of the International Congress of Mathematicians (Vancouver, 1975), 243–249 | MR | Zbl

[6] Ladner R. E., “The computational complexity of provability in systems of modal propositional logic”, SIAM Journal on Computing, 6:3 (1977), 467–480 | DOI | MR | Zbl

[7] Segerberg K., An Essey in Classical Modal Logic, Uppsala, 1971 | MR

[8] Sistla A. P., Clarke E. M., “The complexity of propositional linear temporal logics”, Journal of the ACM, 32:3 (1985), 733–749 | DOI | MR | Zbl

[9] Spaan E., Complexity of modal logics, PhD thesis, 1993 | MR

[10] Statman R., “Intuitionistic propositional logic is polynomial-space complete”, Theoretical Computer Science, 9 (1979), 67–72 | DOI | MR | Zbl

[11] Zakharyaschev M., Wolter F., Chagrov A., “Advanced Modal Logic”, Handbook of Philosophical Logic, v. 3, 2nd edition, eds. D.M. Gabbay, F. Guenthner, Springer, Netherlands, 2001, 83–266 | DOI | MR