论文标题
流词问题
Streaming word problems
论文作者
论文摘要
我们研究有限生成组的单词问题的确定性和随机流算法。对于有限生成的线性群，metabelian组和可溶解组，我们显示了具有对数空间复杂性的随机流算法的存在。我们还表明，在几个组理论构造下，有有限生成的具有Logspace随机流算法的有限生成的组被封闭：有限的扩展，图形产品和花圈产品由免费的Abelian群体。我们将这些结果与几个下限进行对比。汤普森（Thompson）的组$ f $是有限呈现的组的一个示例，其中单词问题只有一个线性空间随机流算法。最后，研究了自由组中的亚组成员问题和自由组的直接产品的随机流媒体算法。
We study deterministic and randomized streaming algorithms for word problems of finitely generated groups. For finitely generated linear groups, metabelian groups and free solvable groups we show the existence of randomized streaming algorithms with logarithmic space complexity for their word problems. We also show that the class of finitely generated groups with a logspace randomized streaming algorithm for the word problem is closed under several group theoretical constructions: finite extensions, graph products and wreath products by free abelian groups. We contrast these results with several lower bound. An example of a finitely presented group, where the word problem has only a linear space randomized streaming algorithm, is Thompson's group $F$. Finally, randomized streaming algorithms for subgroup membership problems in free groups and direct products of free groups are studied.
