chap9.txt

  
  9. Stallings foldings
  
  
  9.1 Some theory
  
  
  9.2 Foldings
  
  A  finitely  generated  subgroup of a finitely generated free group is given
  through  a  list whose first element is the number of generators of the free
  group and the remaining elements are the generators of the subgroup.
  
  A  generator  of  the  subgroup  may be given through a string of letters or
  through a list of positive integers as decribed in what follows.
  
  When  the  free  group  has  n generators, the n+j^th letter of the alphabet
  should  be  used to represent the formal inverse of the j^th generator which
  is  represented  by  the  j^th  letter. The number of generators of the free
  group must not exceed 7.
  
  For  example,  [2,"abc","bbabcd"]  means the subgroup of the free group on 2
  generators  generated  by  aba^-1 and bbaba^-1b^-1. The same subgroup may be
  given as [2,[1,2,3],[2,2,1,2,3,4]]
  
  9.2-1 FlowerAutomaton
  
  > FlowerAutomaton( L ) _____________________________________________function
  
  The  argument  L  is  a  subgroup of the free group given through any of the
  representations described above.
  
  9.2-2 FoldFlowerAutomaton
  
  > FoldFlowerAutomaton( A ) _________________________________________function
  
  Makes identifications on the flower automaton A