J. Birget

activity

19982024

most citedCircuits, coNP-completeness, and the groups of Richard Thompson

18 citations · 42 across the 30 of their papers we have counts for

collaborators

31 papers

math.HO2024

Remembering Mark Sapir

Jean-Camille Birget, Gili Golan, Alexander Olshanskii +1

This memorial article for Mark Sapir provides a brief overview of his life and career. Among his many contributions we highlight two of his most celebrated achievements: his ground…

math.GR2024

Some properties of Higman-Thompson monoids and digital circuits

J. C. Birget

We define various monoid versions of the R. Thompson group $V$ , and prove connections with monoids of acyclic digital circuits. We show that the monoid $M_{2, 1}$ (based on partial…

math.GR2022

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

J. C. Birget

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…

math.GR2021

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

J. C. Birget

The Thompson group $V$ , as well as the Brin-Thompson group $2 V$ , is finitely generated and can be defined as a monoid acting on bitstrings, respectively pairs of bitstrings. Theref…

math.GR2020★ 1 cited

A monoid version of the Brin-Higman-Thompson groups

J. C. Birget

We generalize the Brin-Higman-Thompson groups $n G_{k, 1}$ to monoids $n M_{k, 1}$ , for $n \geq 1$ and $k \geq 2$ , by replacing bijections by partial functions. The monoid $n M_{k, 1}$ …

math.GR2020★ 2 cited

The word problem of the Brin-Higman-Thompson groups

J. C. Birget

We show that the word problem of the Brin-Higman-Thompson group $n G_{k, 1}$ is {\sf coNP}-complete for all $n \geq 2$ and all $k \geq 2$ . For this we prove that $n G_{k, 1}$ is finite…