Space Functions and Space Complexity of the Word Problem in Semigroups

Research paper by A. Yu. Olshanskii

Indexed on: 16 Mar '13Published on: 16 Mar '13Published in: Computational Complexity

Abstract

We introduce the space function s(n) of a finitely presented semigroup $${S =\langle A \mid R \rangle}$$. 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 derivations $${w = w_0 \rightsquigarrow \dots \rightsquigarrow w_t = w'; s(n)}$$ bounds from above the lengths of the words wi at intermediate steps, i.e., the space sufficient to implement all such transitions $${w \rightsquigarrow \dots \rightsquigarrow 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.