Space functions and space complexity of the word problem in semigroups. (Q395608)

In previous work [\textit{A. Yu. Olshanskii}, Trans. Am. Math. Soc. 364, No. 9, 4937-4985 (2012; Zbl 1287.20045)], the author proved a remarkable space complexity analogue to the following theorem due to the author and several coauthors [\textit{J. C. Birget} et al., Ann. Math. (2) 156, No. 2, 467-518 (2002; Zbl 1026.20018)], which itself can be seen as the (time) complexity analogue of the Higman Embedding Theorem: The word problem of a finitely generated group \(G\) is in NP -- i.e. solvable in polynomial time by a nondeterministic Turing machine -- if and only if \(G\) is a subgroup of a finitely presented group with polynomial isoperimetric function. The complexity of word problems can also be studied for semigroups and monoids and in [\textit{J.-C. Birget}, Int. J. Algebra Comput. 8, No. 2, 235-294 (1998; Zbl 0923.20043)] it is shown that the word problem of a finitely generated semigroup is decidable in non-deterministic polynomial time if and only if the semigroup is embeddable into a finitely presented semigroup with polynomial Dehn function. The work under review adds the corresponding space complexity result for semigroups to this family of results: Given a finite presentation \(S\) the space function \(s(n)\) of \(S\) is defined to be the minimal \(m\) such that, for any words \(w,w'\) of length at most \(n\) that represent the same element in the semigroup, there is an \(S\)-derivation from \(w\) to \(w'\) so that all words in this derivation are of length at most \(m\). With this definition 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. (The same statement is also proven for monoids.) Space functions of groups could be defined in the same manner and in fact the main result of this paper sounds similar to the corresponding space complexity result mentioned above. But using the algebraic structure of groups several modified space functions could be defined and, in fact, the definition used in [\textit{A. Yu. Olshanskii}, loc. cit.] is one of these modifications. The author claims that it is an open question if the space complexity result for groups is valid using the definition of space functions given above.