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

2022/03/16 by J. C. Birget, Birget, J. C.
Computer Science · Mathematics · #Algebraic structures and combinatorial models #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Geometric and Algebraic Topology #Group Theory (math.GR) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2203.08592

openalex publication_date 2022/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 quadratic time-complexity on a deterministic multitape Turing machine, and belongs to logDCFL.

Related

• The groups of Richard Thompson and complexity
• Context-Freeness of Higman-Thompson group's co-word problem
• The word problem of the Brin-Thompson group is coNP-complete
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• Groups that do and do not have context-sensitive word problem