Geodesic
Computational complexity of the word problem in modal algebras
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2021), pp. 5-17 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper deals with the word problem for modal algebras. It is proved that, for the variety of all modal algebras, the word problem is $\mathrm{PSPACE}$-complete if only constant modal terms or only $0$-generated modal algebras are considered. We also consider the word problem for different varieties of modal algebras. It is proved that the word problem for a variety of modal algebras can be $C$-hard, for any complexity class or unsolvability degree $C$ containing a $C$-complete problem. It is shown how to construct such varieties.
Mots-clés : modal algebra
Keywords: word equality problem, computational complexity. 
@article{VTPMK_2021_3_a0,
     author = {M. N. Rybakov},
     title = {Computational complexity of the word problem in modal algebras},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {5--17},
     year = {2021},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2021_3_a0/}
}
TY  - JOUR
AU  - M. N. Rybakov
TI  - Computational complexity of the word problem in modal algebras
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2021
SP  - 5
EP  - 17
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2021_3_a0/
LA  - ru
ID  - VTPMK_2021_3_a0
ER  - 
%0 Journal Article
%A M. N. Rybakov
%T Computational complexity of the word problem in modal algebras
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2021
%P 5-17
%N 3
%U http://geodesic.mathdoc.fr/item/VTPMK_2021_3_a0/
%G ru
%F VTPMK_2021_3_a0
M. N. Rybakov. Computational complexity of the word problem in modal algebras. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2021), pp. 5-17. http://geodesic.mathdoc.fr/item/VTPMK_2021_3_a0/

[1] Adian S. I., Durnev V. G., “Decision problems for groups and semigroups”, Russian Mathematical Surveys, 55:2 (2000), 207–296 | DOI | MR | Zbl

[2] Levin L. A., “Universal sequential search problems”, Problems of Information Transmission, 9:3 (1973), 265–266 | MR | Zbl

[3] Markov A. A., “The impossibility of some algorithms in the theory of associative systems”, Soviet Mathematics. Doklady, 55:7 (1947), 587–590 (in Russian)

[4] Rybakov M. N., “The complexity of a constant fragment of propositional dynamic logic”, Herald of Tver State University. Series: Applied Mathematics, 2007, no. 5, 5–17 (in Russian)

[5] Rybakov M. N., “Algorithmical properties of quasinormal modal logics with linear finite model property”, Herald of Tver State University. Series: Applied Mathematics, 2018, no. 4, 87–97 (in Russian) | DOI

[6] Chagrov A., Rybakov M., “How many variables does one need to prove PSPACE-hardness of modal logics?”, Advances in Modal Logic, 2003, no. 4, 71–82 | Zbl

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

[8] Halpern J. Y., “The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic”, Aftificial Intelligence, 75:2 (1995), 361–372 | DOI | Zbl

[9] 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

[10] Papadimitriou C. H., Computational Complexity, Addison–Wesley Publishing Company, 1995

[11] Post E. L., “Recursive unsolvability of a problem of Thue”, Journal of Symbolic Logic, 12:1 (1947), 1–11 | DOI | MR | Zbl

[12] Rybakov M., “Complexity of finite-variable fragments of EXPTIME-complete logics”, Journal of Applied Non-Classical Logics, 17:3 (2007), 359–382 | DOI | MR | Zbl

[13] Rybakov M., Shkatov D., “Complexity and expressivity of branching- and alternating-time temporal logics with finitely many variables”, Theoretical Aspects of Computing, Lecture Notes in Computer Science, eds. B. Fischer, T. Uustalu, Springer, 2018, 396–414 | DOI | MR | Zbl

[14] Rybakov M., Shkatov D., “Complexity and expressivity of propositional dynamic logics with finitely many variables”, Logic Journal of the IGPL, 26:5 (2018), 539–547 | DOI | MR

[15] Rybakov M., Shkatov D., “On relationship between complexity function and complexity of validity in propositional modal logic”, Logical Perspectives 2021 (Moscow, June 7 – July 8)

[16] Shoenfield J. R., Degrees of unsolvability, North-Holland Publishing Company; American Elsevier Publishing Company, 1971 | Zbl

[17] Spaan E., Complexity of modal logics, PhD thesis, Universiteit van Amsterdam, 1993

[18] Thue A., “Problem über Veränderungen von Zeichenreihen nach gegebehen Regeln”, Videnskapsselskapets Skrifter. I. Mat.-Naturv. Klasse, 1914, no. 10