Geodesic
On complexity of the word problem in semigroups with homogeneous relations
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 55-61.

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

In this paper we study the computational complexity of the word problem in semigroups with the condition of homogeneity of the defining relations. These are finitely defined semigroups, in which for each defining relation the lengths of the left and right parts are equal. The word problem for such semigroups is decidable, but known algorithms require exponential time and memory. We prove that this problem belongs to the class PSPACE, consisting of algorithmic problems that are solved by Turing machines using space (memory cells) bounded polynomially. This improves the upper bound on the space complexity known before. On the other hand, we prove that there exists a semigroup with the condition of homogeneity of defining relations, in which the equality problem is complete in the class PSPACE with respect to polynomial reducibility. It is assumed (although not proven) that the class PSPACE is wider than the class NP and, even more so, the class P. Thus, it is shown that there are semigroups with the condition of homogeneity of defining relations with the intractable problem of equality.
Keywords: computational complexity, semigroups, word problem. 
@article{SEMR_2024_21_1_a1,
     author = {A. N. Rybalov},
     title = {On complexity of the word problem in semigroups with homogeneous relations},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {55--61},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a1/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On complexity of the word problem in semigroups with homogeneous relations
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - 55
EP  - 61
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a1/
LA  - ru
ID  - SEMR_2024_21_1_a1
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On complexity of the word problem in semigroups with homogeneous relations
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P 55-61
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a1/
%G ru
%F SEMR_2024_21_1_a1
A. N. Rybalov. On complexity of the word problem in semigroups with homogeneous relations. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 55-61. http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a1/