Space functions and complexity of the word problem in semigroups

2011/11/06 by Olshanskii, Alexander
#03D10 #03D40 #20F09 #20F69 #20M05 #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.1111.1458

Abstract

We introduce the space function s(n) of a finitely presented semigroup S =. To define s(n) we consider pairs of words w,w' over A of length at most n equal in S and use relations from R for the transformations w=w₀→...→ w_t= w'; s(n) bounds from above the tape space (or computer memory) sufficient to implement all such transitions w→...→ w'. One of the results obtained is the following criterion: A finitely generated semigroup S has decidable word problem of polynomial space complexity if and only if S is a subsemigroup of a finitely presented semigroup H with polynomial space function.

Related

• Space functions of groups
• Space functions of groups
• The word problem for free adequate semigroups
• Concrete algorithms for word problem and subsemigroup problem for\n semigroups which are disjoint unions of finitely many copies of the free\n monogenic semigroup
• Functions on groups and computational complexity