论文标题
关于R. Thompson Group V的复杂性
On the complexity of the word problem of the R. Thompson group V
论文作者
论文摘要
我们分析了Lehnert和Schweitzer的证据表明，Thompson Group V的单词问题是无共同的，我们表明这个词问题是反向确定性无上下文无上下文的循环结合的循环封闭的补充。对于某些有限生成集，这个词问题是四种无上下文语言的联合循环封闭的补充。因此，$ v $单词问题的确定性时间复杂性最多是二次的。
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. For certain finite generating sets, this word problem is the complement of the cyclic closure of the union of four deterministic context-free languages. It follows that the deterministic time-complexity of the word problem of $V$ is at most quadratic.
