JBJean-Camille Birget
Jean-Camille Birget
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Jean-Camille Birget has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
- Eliyahu Rips
The Hebrew University of Jerusalem
2 shared publications - A. Yu. Ol'SHanskii
Moscow State University
1 shared publication - John C. Meakin
University of Nebraska-Lincoln
1 shared publication Joseph B. Stephen
Department of Mathematical Sciences, Northern Illinois University, DeKalb, IL 60115-2888, USA
1 shared publicationM. Sapir
1 shared publicationMark Sapir
1 shared publication
Latest Publications
- 1 April 2000
- Published by Elsevier in Theoretical Computer Science
- Vol. 237 (1-2) , 81-104
Reductions and functors from problems to word problems
- 1 April 2000
- Published by Elsevier in Theoretical Computer Science
- Vol. 237 (1-2) , 81-104
Reductions and functors from problems to word problems
- Open Access
Isoperimetric Functions of Groups and Computational Complexity of the Word Problem
We prove that the word problem of a finitely generated group $G$ is in NP (solvable in polynomial time by a non-deterministic Turing machine) if and only if this group is a subgroup of a finitely presented group $H$ with polynomial isoperimetric function. The embedding can be chosen in such a way that $G$ has bounded distortion in $H$.Open AccessIsoperimetric Functions of Groups and Computational Complexity of the Word Problem
We prove that the word problem of a finitely generated group $G$ is in NP (solvable in polynomial time by a non-deterministic Turing machine) if and only if this group is a subgroup of a finitely presented group $H$ with polynomial isoperimetric function. The embedding can be chosen in such a way that $G$ has bounded distortion in $H$. - Open Access
Isoperimetric and isodiametric functions of groups
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 every $m$ the first $m$ digits of a real number $\alpha\ge 4$ are computable in time $\le C2^{2^{Cm}}$ for some constant $C>0$ then $n^\alpha$ is equivalent (``big O'') to the Dehn function of a finitely presented group. The smallest isodiametric function of this group is $n^{3/4\alpha}$. On the other hand if $n^\alpha$ is equivalent to the Dehn function of a finitely presented group then the first $m$ digits of $\alpha$ are computable in time $\le C2^{2^{2^{Cm}}}$ for some constant $C$. This implies that, say, functions $n^{\pi+1}$, $n^{e^2}$ and $n^\alpha$ for all rational numbers $\alpha\ge 4$ are equivalent to the Dehn functions of some finitely presented group and that $n^\pi$ and $n^\alpha$ for all rational numbers $\alpha\ge 3$ are equivalent to the smallest isodiametric functions of finitely presented groups. Moreover we describe all Dehn functions of finitely presented groups $\succ n^4$ as time functions of Turing machines modulo two conjectures: \begin{enumerate} \item Every Dehn function is equivalent to a superadditive function. \item The square root of the time function of a Turing machine is equivalent to the time function of a Turing machine. \end{enumerate}Open AccessIsoperimetric and isodiametric functions of groups
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 every $m$ the first $m$ digits of a real number $\alpha\ge 4$ are computable in time $\le C2^{2^{Cm}}$ for some constant $C>0$ then $n^\alpha$ is equivalent (``big O'') to the Dehn function of a finitely presented group. The smallest isodiametric function of this group is $n^{3/4\alpha}$. On the other hand if $n^\alpha$ is equivalent to the Dehn function of a finitely presented group then the first $m$ digits of $\alpha$ are computable in time $\le C2^{2^{2^{Cm}}}$ for some constant $C$. This implies that, say, functions $n^{\pi+1}$, $n^{e^2}$ and $n^\alpha$ for all rational numbers $\alpha\ge 4$ are equivalent to the Dehn functions of some finitely presented group and that $n^\pi$ and $n^\alpha$ for all rational numbers $\alpha\ge 3$ are equivalent to the smallest isodiametric functions of finitely presented groups. Moreover we describe all Dehn functions of finitely presented groups $\succ n^4$ as time functions of Turing machines modulo two conjectures: \begin{enumerate} \item Every Dehn function is equivalent to a superadditive function. \item The square root of the time function of a Turing machine is equivalent to the time function of a Turing machine. \end{enumerate} - 1 January 1998
- Published by Springer Nature in Semigroup Forum
- Vol. 56 (1) , 150
First Announcement International Conference on Algorithmic Problems in Groups and Semigroups (ICAPGS)
- 1 January 1998
- Published by Springer Nature in Semigroup Forum
- Vol. 56 (1) , 150
First Announcement International Conference on Algorithmic Problems in Groups and Semigroups (ICAPGS)
- 1 June 1996
- Published by Springer Nature in Theory of Computing Systems
- Vol. 29 (3) , 191-226
Two-way automata and length-preserving homomorphisms
- 1 June 1996
- Published by Springer Nature in Theory of Computing Systems
- Vol. 29 (3) , 191-226
Two-way automata and length-preserving homomorphisms
- 26 September 1994
- Published by Elsevier in Theoretical Computer Science
- Vol. 132 (1-2) , 243-258
Formal languages defined by uniform substitutions
- 26 September 1994
- Published by Elsevier in Theoretical Computer Science
- Vol. 132 (1-2) , 243-258
Formal languages defined by uniform substitutions
- 1 September 1993
- Published by Springer Nature in Theory of Computing Systems
- Vol. 26 (3) , 237-269
State-complexity of finite-state devices, state compressibility and incompressibility
- 1 September 1993
- Published by Springer Nature in Theory of Computing Systems
- Vol. 26 (3) , 237-269
State-complexity of finite-state devices, state compressibility and incompressibility