Geodesic
Computational complexity of the word problem in modal algebras
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2021), pp. 5-17

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

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},
     publisher = {mathdoc},
     number = {3},
     year = {2021},
     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
PB  - mathdoc
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
%I mathdoc
%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/