|
Computational complexity of the word problem in modal and pseudo-Boolean algebras
with a small number of generators
M. Rybakov Tver State University, 33 Zhelyabova str., Tver, 170100 Russia
Abstract:
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, modal algebra, Heyting algebra, pseudo-Boolean algebra, finitely generated algebra.
Received: 25.07.2021 Revised: 21.08.2021 Accepted: 29.09.2021
Citation:
M. Rybakov, “Computational complexity of the word problem in modal and pseudo-Boolean algebras
with a small number of generators”, Izv. Vyssh. Uchebn. Zaved. Mat., 2022, no. 5, 42–60; Russian Math. (Iz. VUZ), 66:5 (2022), 33–48
Linking options:
https://www.mathnet.ru/eng/ivm9774 https://www.mathnet.ru/eng/ivm/y2022/i5/p42
|
Statistics & downloads: |
Abstract page: | 128 | Full-text PDF : | 32 | References: | 30 | First page: | 6 |
|