Evaluation problems for the Thompson group and the Brin-Thompson group, and their relation to the word problem
Jean-Camille Birget
Abstract
Open-access reader
Jean-Camille Birget
Abstract
Open-access reader
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$.
A significance statement is not available in the OpenAlex record.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
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$.
Key concepts: Word problem (mathematics education), Word (group theory), Group (periodic table), Context (archaeology), Relation (database), Monoid, Mathematics, Computer science