Can I read On the complexity of the word problem of the R. Thompson group V on EtoBox?

On the complexity of the word problem of the R. Thompson group V by Birget, J. C. is a scholarly article available to read on EtoBox.

What is On the complexity of the word problem of the R. Thompson group V about?

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.

Author

Birget, J. C.

Published

2022

Language

EN