On the complexity of the word problem of the R. Thompson group V

03/16/2022

∙

by   J. C. Birget, et al.

∙

0

∙

share

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.