|
This article is cited in 1 scientific paper (total in 1 paper)
Theoretical Foundations of Computer Science
Computational complexity of the word problem in modal algebras
M. N. Rybakovabc a Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Moscow
b National Research University "Higher School of Economics", Moscow
c Tver State University, Tver
Abstract:
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.
Keywords:
modal algebra, word equality problem, computational complexity.
Received: 04.08.2021 Revised: 17.08.2021 Accepted: 27.10.2021
Citation:
M. N. Rybakov, “Computational complexity of the word problem in modal algebras”, Vestnik TVGU. Ser. Prikl. Matem. [Herald of Tver State University. Ser. Appl. Math.], 2021, no. 3, 5–17
Linking options:
https://www.mathnet.ru/eng/vtpmk619 https://www.mathnet.ru/eng/vtpmk/y2021/i3/p5
|
Statistics & downloads: |
Abstract page: | 209 | Full-text PDF : | 109 | References: | 41 |
|