On the complexity of the word problem of the R. Thompson group V
J.C. Birget
我们分析了Lehnert和Schweitzer的证明,Thompson group V的单词问题是共同无上下文的,我们表明这个词问题是反向确定性上下文自由语言结合循环闭合的补充。 对于任何有限生成的 V 子组也是如此。 对于某些有限生成集,这个单词问题是四种确定性上下文自由语言的结合循环闭合的补充。 因此,V的单词问题在确定性多带图uring机器上具有二次时间复杂度,属于logDCFL。
We analyze the proof by Lehnert and Schweitzer that the word problem of the Thompson group V is co-context-free, and we show that this word problem is the complement of the cyclic closure of a union of reverse deterministic context-free languages. The same is true for any finitely generated subgroup of V. For certain finite generating sets, this word problem is the complement of the cyclic closure of the union of four deterministic context-free languages. Therefore the word problem of V has quad...
