18 citations · 18 across the 2 of their papers we have counts for
6 papers · 1 filter
Circuits, coNP-completeness, and the groups of Richard Thompson
Jean-Camille Birget
We construct a finitely presented group with coNP-complete word problem, and a finitely generated simple group with coNP-complete word problem. These groups are represented as Thom…
The groups of Richard Thompson and complexity
Jean-Camille Birget
We prove new results about the remarkable infinite simple groups introduced by Richard Thompson in the 1960s. We define the groups as partial transformation groups and we give a fa…
Functions on groups and computational complexity
Jean-Camille Birget
We give some connections between various functions defined on finitely presented groups (isoperimetric, isodiametric, Todd-Coxeter radius, filling length functions, etc.), and we s…
A complete rewrite system and normal forms for (S)_reg
Jean-Camille Birget, Stuart W. Margolis
The (.)_reg construction was introduced in order to make an arbitrary semigroup S divide a regular semigroup (S)_reg which shares some important properties with S (e.g., finiteness…
Isoperimetric Functions of Groups and Computational Complexity of the Word Problem
J. -C. Birget, A. Yu. Olshanskii, E. Rips +1
We prove that the word problem of a finitely generated group is in NP (solvable in polynomial time by a non-deterministic Turing machine) if and only if this group is a subgrou…
Isoperimetric and isodiametric functions of groups
Mark Sapir, Jean-Camille Birget, Eliyahu Rips
This is the first of two papers devoted to connections between asymptotic functions of groups and computational complexity. One of the main results of this paper states that if for…