科研之友
微信
新浪微博
Facebook
分享链接
摘要
We introduce the space function s(n) of a finitely presented semigroup . 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 bounds from above the lengths of the words w (i) at intermediate steps, i.e., the space sufficient to implement all such transitions . 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.
- 出版日期2013-12
