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


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.