Geodesic
Computational complexity of the word problem in modal and pseudo-Boolean algebras
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 5 (2022), pp. 42-60

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

We consider the computational complexity of the word problem for finitely generated Heyting and modal algebras. It is shown that the word problem is PSPACE-complete if only constant modal terms or only $0$-generated modal algebras are considered; similar results are obtained for two-variable terms and $2$-generated Heyting algebras. It is also shown that, if an equation of positive terms is refuted in a Heyting algebra, it is refuted in a $2$-generated algebra. We also consider the word problem for certain classes of modal and Heyting algebras and obtain results similar to those mentioned above for infinite families of such classes. The obtained results are optimal in the number of generators: reduction in generators leads to the polynomial time decidable word problem.
Keywords: word problem, finitely generated algebra.
Mots-clés : modal algebra, Heyting algebra, pseudo-Boolean algebra 
@article{IVM_2022_5_a3,
     author = {M. Rybakov},
     title = {Computational complexity of the word problem in modal and {pseudo-Boolean} algebras},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {42--60},
     publisher = {mathdoc},
     number = {5},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2022_5_a3/}
}
TY  - JOUR
AU  - M. Rybakov
TI  - Computational complexity of the word problem in modal and pseudo-Boolean algebras
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2022
SP  - 42
EP  - 60
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2022_5_a3/
LA  - ru
ID  - IVM_2022_5_a3
ER  - 
%0 Journal Article
%A M. Rybakov
%T Computational complexity of the word problem in modal and pseudo-Boolean algebras
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2022
%P 42-60
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2022_5_a3/
%G ru
%F IVM_2022_5_a3
M. Rybakov. Computational complexity of the word problem in modal and pseudo-Boolean algebras. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 5 (2022), pp. 42-60. http://geodesic.mathdoc.fr/item/IVM_2022_5_a3/