foldings.gd

#############################################################################
##
#W  foldings.gd                       Manuel Delgado <[email protected]>
#W                                    Jose Morais    <[email protected]>
##
#H  @(#)$Id: foldings.gd,v 1.13 $
##
#Y  Copyright (C)  2004,  CMUP, Universidade do Porto, Portugal
##
#############################################################################
## A finitely generated subgroup of a free group of finite rank rk can be given
## as a list [rk, gen1, gen2,...]. The generators can be given as strings
## on the generators of the free group (and its inverses which are 
## represented by the corresponding capital letters) or as lists of integers
## where if i<=rk then  i represents the ith generator; if i>rk, then i
## represents the inverse of the rk-ith generator. The generators of the 
## free group are assumed to be a, b, c, ...
##
## Example: [2,"abA","bbabAB"] means the subgroup of the free group on 2 
## generators generated by aba^{-1} ...
##
## Another representation could be [2,[1,2,3],[2,2,1,2,3,4]].
##
#############################################################################
##
#F IsGenRep(L)
##
DeclareGlobalFunction( "IsGenRep" );
#############################################################################
##
#F IsListRep(L)
##
DeclareGlobalFunction( "IsListRep" );
#############################################################################
## The following functions allow us to pass from one representation to 
## another
##
#############################################################################
##
#F GeneratorsToListRepresentation(L)
##
## L is a list whose first element is the number of generators of the 
## free group. The remaining elements are the generators of the subgroup. 
##
## Example: when the input is [2,"abA","bbabAB"], the output will be
## [2,[1,2,3],[2,2,1,2,3,4]]
##
## Warning: Alphabets with more than 7 letters must not be used 
DeclareGlobalFunction( "GeneratorsToListRepresentation" );
#############################################################################
#F  ListToGeneratorsRepresentation(K) # is the inverse of 
## GeneratorsToListRepresentation
DeclareGlobalFunction( "ListToGeneratorsRepresentation" );
###############################################################################
##
#F FlowerAutomaton(L)
##
## Given a finitely generated subgroup of a free group (by any of the two 
## means indicated above) the flower automaton is constructed.
##
DeclareGlobalFunction( "FlowerAutomaton" );
#############################################################################
##
#F FoldFlowerAutomaton(A)
## Makes Stalings foldings on the flower automaton <A>
##
DeclareGlobalFunction( "FoldFlowerAutomaton" );
#############################################################################
##
#F SubgroupGenToInvAut(L)
##
## Returns the inverse automaton corresponding to the subgroup given by 
## <A>L</A>.
DeclareGlobalFunction( "SubgroupGenToInvAut" );
#############################################################################
##
#F AddInverseEdgesToInverseAutomaton(aut)
##
## Given an inverse automaton, adds the edges labeled by the inverses
##
DeclareGlobalFunction( "AddInverseEdgesToInverseAutomaton" );
#############################################################################
##
#F GeodesicTreeOfInverseAutomatonWithInformation
##
## Is an auxiliar function to the following functions
## InverseAutomatonToGenerators and GeodesicTreeOfInverseAutomaton
##
DeclareGlobalFunction( "GeodesicTreeOfInverseAutomatonWithInformation" );
#############################################################################
##
#F GeodesicTreeOfInverseAutomaton
##
## Returns an automaton whose underlying graph is a geodesic tree of the 
## underlying graph of the automaton given.
##
DeclareGlobalFunction( "GeodesicTreeOfInverseAutomaton" );

#############################################################################
##
#F InverseAutomatonToGenerators
##
## returns a set of generators (given trough the representation above) of the 
## subgroup of the free group corresponding to the automaton given. 
##
DeclareGlobalFunction( "InverseAutomatonToGenerators" );