Page d'accueil du CNRS Page d'accueil de Paris Diderot Page d'accueil du LIAFA
LIAFA
Laboratoire d'Informatique Algorithmique: Fondements et Applications
CNRS UMR 7089, Université Paris Diderot - Paris 7, Case 7014
75205 Paris Cedex 13 - Tél: +33(0)1.57.27.92.56 - Fax: +33(0)1.57.27.94.09
Page d'accueil de la fondation Sciences Mathématiques de Paris Page d'accueil de FRMPC
   Staff      Contact      How to get to LIAFA      Teaching      Webmail   


Version française

Research reports

  • Report number: 1995-045
  • Authors: V. GUBA, M. SAPIR
  • Title: Diagram groups
  • Summary:


     A diagram group consists of so called spherical semigroup diagrams, that is, labelled plain graphs of some special kind. Semigroup diagrams are geometric images of derivations under Thue systems. The diagram groups measure the number of ways to derive one word from another word in a given Thue system, that is they measure the non-asphericily of a Thue system. We describe (by generators and defining relations) diagram groups corresponding to complete (confluent and terminating) Thue systems. This allowed us to answer some questions of Pride about aspherical monoid presentations. Diagram groups are interesting in their own. There exists a very fast algorithm of multiplying diagrams, so groups representable by diagrams have nicely solvable word problems. The class of diagram groups turned out to be wide. It includes all free groups, the so called Thompson groups, is closed under direct and free products and under some other constructions. In some sense diagram groups are 2-dimensional analogues of free groups. We develop combinatorics on diagrams which resembles the combinatorics on words. This allowed us to establish many structure properties of diagram groups.


 
 ©  LIAFA 1995, Last updating: 2013, May webmestre[at]liafa.univ-paris-diderot.fr