Evaluation problems for the Thompson group and the Brin-Thompson group, and their relation to the word problem

2021/11/16 by Jean-Camille Birget, Birget, J. C.
Computer Science · Mathematics · #Advanced Operator Algebra Research #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.2111.08646

openalex publication_date 2021/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Thompson group V, as well as the Brin-Thompson group 2V, is finitely generated and can be defined as a monoid acting on bitstrings, respectively pairs of bitstrings. Therefore evaluation problems can be defined for V and 2V. We show that these evaluation problems reduce to the corresponding word problems, and that in general, these evaluation problems are actually equivalent to the word problems. The long-input version of the evaluation problem is deterministic context-free and reverse deterministic context-free for V, and P-complete for 2V.

Related

• The word problem of the Brin-Thompson group is coNP-complete
• On the complexity of the word problem of the R. Thompson group V
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• The word problem of the Brin-Higman-Thompson groups
• Circuits, coNP-completeness, and the groups of Richard Thompson