Functionally recursive groups
  
  
                              Self-similar groups
  
  
                               Version 0.857142p8
  
  
                          $Date: 2008/12/02 12:04:31 $
  
  
                               Laurent Bartholdi
  
  
  
            Groups  generated  by  automata or satisfying functional
            recursions
  
  
  
  Laurent Bartholdi
      Email:    mailto:laurent.bartholdi@gmail.com
      Homepage: http://www.uni-math.gwdg.de/laurent/
  
  
  Address: Mathematisches Institut, Bunsenstraße 3-5, D-37073 Göttingen
           D-37073 Göttingen
           Germany
  
  
  -------------------------------------------------------
  Abstract
  This  document  describes  the package FR, which implements in GAP the basic
  objects of Mealy machines and functional recursions; and handles groups that
  they generate.
  
  Groups  defined by a recursive action on a rooted tree can be defined in GAP
  via  their recursion. Various algorithms are implemented to manipulate these
  groups and their elements.
  
  For  comments  or questions on FR please contact the author; this package is
  still under development.
  
  
  -------------------------------------------------------
  Copyright
  © 2006-2008 by Laurent Bartholdi
  
  
  -------------------------------------------------------
  Acknowledgements
  Part  of  this  work is supported by the "Swiss National Fund for Scientific
  Research"
  
  
  -------------------------------------------------------
  Colophon
  This  project  started  in  the mid-1990s, when, as a PhD student I did many
  calculations   with   groups   generated   by  automata,  and  realized  the
  similarities  between  all  calculations; it quickly became clear that these
  calculations could be done much better by a computer than by a human.
  
  The  first routines I wrote constructed finite representations of the groups
  considered,  so  as  to  get  insight from fast calculations within GAP. The
  results  then  had  to  be  proved  correct  within the infinite group under
  consideration,  and  this  often  involved guessing appropriate words in the
  infinite group with a given image in the finite quotient.
  
  Around  2000,  I  had developed quite a few routines, which I assembled in a
  GAP  package,  that  dealt  directly  with infinite groups. This package was
  primitive at its core, but was extended with various routines as they became
  useful.
  
  I  decided  in  late  2005  to  start a new package from scratch, that would
  encorporate  as  much  functionality  as  possible in a uniform manner; that
  would  handle  semigroups  as well as groups; that could be easily extended;
  and  with  a complete, understandable documentation. I hope I am not too far
  from these objectives.
  
  
  -------------------------------------------------------
  
  
  Contents (FR)
  
  1 Licensing
  2 FR package
    2.1 A brief mathematical introduction
    2.2 An example session
  3 Functionally recursive machines
    3.1 Types of machines
    3.2 Products of machines
    3.3 Creators for FRMachines
      3.3-1 FRMachineNC
      3.3-2 FRMachine
      3.3-3 UnderlyingFRMachine
      3.3-4 AsGroupFRMachine
      3.3-5 ChangeFRMachineBasis
    3.4 Attributes for FRMachines
      3.4-1 StateSet
      3.4-2 GeneratorsOfFRMachine
      3.4-3 Output
      3.4-4 Transition
      3.4-5 WreathRecursion
    3.5 Operations for FRMachines
      3.5-1 StructuralGroup
      3.5-2 \+
      3.5-3 \*
      3.5-4 TensorSumOp
      3.5-5 TensorProductOp
      3.5-6 DirectSumOp
      3.5-7 DirectProductOp
      3.5-8 TreeWreathProduct
      3.5-9 SubFRMachine
      3.5-10 Minimized
      3.5-11 Correspondence
  4 Functionally recursive elements
    4.1 Creators for FRElements
      4.1-1 FRElementNC
      4.1-2 FRElement
      4.1-3 FRElement
      4.1-4 ComposeElement
      4.1-5 VertexElement
      4.1-6 DiagonalElement
      4.1-7 AsGroupFRElement
    4.2 Operations and Attributes for FRElements
      4.2-1 Output
      4.2-2 Activity
      4.2-3 Transition
      4.2-4 Portrait
      4.2-5 DecompositionOfFRElement
      4.2-6 StateSet
      4.2-7 State
      4.2-8 States
      4.2-9 FixedStates
      4.2-10 LimitStates
      4.2-11 IsFiniteStateFRElement
      4.2-12 InitialState
      4.2-13 \^
      4.2-14 \*
      4.2-15 \[\]
  5 Mealy machines and elements
    5.1 Creators for MealyMachines and MealyElements
      5.1-1 MealyMachine
      5.1-2 MealyMachine
      5.1-3 MealyMachineNC
      5.1-4 AllMealyMachines
    5.2 Operations and Attributes for MealyMachines and MealyElements
      5.2-1 Draw
      5.2-2 Minimized
      5.2-3 DualMachine
      5.2-4 IsReversible
      5.2-5 IsMinimized
      5.2-6 AlphabetInvolution
      5.2-7 IsBireversible
      5.2-8 StateGrowth
      5.2-9 Degree
      5.2-10 IsFinitaryFRElement
      5.2-11 Depth
      5.2-12 IsBoundedFRElement
      5.2-13 IsPolynomialGrowthFRElement
      5.2-14 Signatures
      5.2-15 VertexTransformationsFRMachine
      5.2-16 FixedRay
      5.2-17 IsLevelTransitive
      5.2-18 AsMealyMachine
      5.2-19 AsMealyMachine
      5.2-20 AsMealyElement
      5.2-21 AsIntMealyMachine
      5.2-22 TopElement
      5.2-23 ConfinalityClasses
      5.2-24 Germs
      5.2-25 HasOpenSetConditionFRElement
      5.2-26 LimitMachine
      5.2-27 NucleusMachine
      5.2-28 GuessMealyElement
  6 Linear machines and elements
    6.1 Methods and operations for LinearFRMachines and LinearFRElements
      6.1-1 VectorMachine
      6.1-2 AlgebraMachine
      6.1-3 Transition
      6.1-4 Transitions
      6.1-5 NestedMatrixState
      6.1-6 ActivitySparse
      6.1-7 Activities
      6.1-8 IsConvergent
      6.1-9 TransposedFRElement
      6.1-10 LDUDecompositionFRElement
      6.1-11 GuessVectorElement
      6.1-12 AsLinearMachine
      6.1-13 AsVectorMachine
      6.1-14 AsAlgebraMachine
      6.1-15 AsVectorMachine
      6.1-16 AsAlgebraMachine
  7 Self-similar groups, monoids and semigroups
    7.1 Creators for FR semigroups
      7.1-1 FRGroup
      7.1-2 SCGroup
      7.1-3 Correspondence
      7.1-4 FullSCGroup
      7.1-5 FRMachineFRGroup
      7.1-6 IsomorphismFRGroup
      7.1-7 IsomorphismMealyGroup
      7.1-8 FRGroupByVirtualEndomorphism
      7.1-9 TreeWreathProduct
      7.1-10 WeaklyBranchedEmbedding
    7.2 Operations for FR semigroups
      7.2-1 PermGroup
      7.2-2 PcGroup
      7.2-3 TransMonoid
      7.2-4 TransSemigroup
      7.2-5 EpimorphismGermGroup
      7.2-6 StabilizerImage
      7.2-7 LevelStabilizer
      7.2-8 IsStateClosedFRSemigroup
      7.2-9 StateClosure
      7.2-10 IsRecurrentFRSemigroup
      7.2-11 IsLevelTransitive
      7.2-12 IsInfinitelyTransitive
      7.2-13 IsFinitaryFRSemigroup
      7.2-14 Degree
      7.2-15 HasOpenSetConditionFRSemigroup
      7.2-16 IsContracting
      7.2-17 NucleusOfFRSemigroup
      7.2-18 NucleusMachine
      7.2-19 BranchingSubgroup
      7.2-20 FindBranchingSubgroup
      7.2-21 IsBranched
      7.2-22 IsBranchingSubgroup
      7.2-23 TopVertexTransformations
      7.2-24 VertexTransformations
      7.2-25 VirtualEndomorphism
      7.2-26 EpimorphismFromFpGroup
      7.2-27 IsomorphismSubgroupFpGroup
    7.3 Properties for infinite groups
      7.3-1 IsTorsionGroup
      7.3-2 IsTorsionFreeGroup
      7.3-3 IsAmenableGroup
      7.3-4 IsVirtuallySimpleGroup
      7.3-5 IsResiduallyFinite
      7.3-6 IsSQUniversal
      7.3-7 IsJustInfinite
  8 Algebras
    8.1 Creators for FR algebras
      8.1-1 FRAlgebra
      8.1-2 SCAlgebra
      8.1-3 BranchingIdeal
    8.2 Operations for FR algebras
      8.2-1 MatrixQuotient
      8.2-2 ThinnedAlgebra
      8.2-3 Nillity
  9 Iterated monodromy groups
    9.1 Creators and operations for IMG FR machines
      9.1-1 IMGFRMachine
      9.1-2 IMGRelator
      9.1-3 Mating
      9.1-4 PolynomialFRMachine
      9.1-5 DBRationalIMGGroup
      9.1-6 ValueRational
      9.1-7 CriticalValuesQuadraticRational
      9.1-8 CanonicalQuadraticRational
      9.1-9 PostCriticalMachine
    9.2 Spiders
      9.2-1 RationalFunction
      9.2-2 IMGFRMachine
  10 Examples
    10.1 Examples of groups
      10.1-1 FullBinaryGroup
      10.1-2 BinaryKneadingGroup
      10.1-3 BasilicaGroup
      10.1-4 AddingGroup
      10.1-5 BinaryAddingGroup
      10.1-6 MixerGroup
      10.1-7 SunicGroup
      10.1-8 GrigorchukMachines
      10.1-9 GrigorchukMachine
      10.1-10 GrigorchukOverGroup
      10.1-11 GrigorchukEvilTwin
      10.1-12 BrunnerSidkiVieiraGroup
      10.1-13 AleshinGroups
      10.1-14 AleshinGroup
      10.1-15 BabyAleshinGroup
      10.1-16 SidkiFreeGroup
      10.1-17 GuptaSidkiGroups
      10.1-18 GuptaSidkiGroup
      10.1-19 NeumannGroup
      10.1-20 FabrykowskiGuptaGroup
      10.1-21 OtherSpinalGroup
      10.1-22 GammaPQMachine
      10.1-23 HanoiGroup
      10.1-24 DahmaniGroup
      10.1-25 MamaghaniGroup
      10.1-26 WeierstrassGroup
      10.1-27 FRAffineGroup
      10.1-28 CayleyGroup
    10.2 Examples of semigroups
      10.2-1 I2Machine
      10.2-2 I4Machine
    10.3 Examples of algebras
      10.3-1 PSZAlgebra
      10.3-2 GrigorchukThinnedAlgebra
      10.3-3 GuptaSidkiThinnedAlgebra
      10.3-4 SidkiFreeAlgebra
    10.4 Bacher's determinant identities
    10.5 VH groups
      10.5-1 VHStructure
      10.5-2 VerticalAction
      10.5-3 VHGroup
      10.5-4 IsIrreducibleVHGroup
      10.5-5 MaximalSimpleSubgroup
  11 FR implementation details
    11.1 The family of FR objects
      11.1-1 FRMFamily
      11.1-2 FREFamily
      11.1-3 AlphabetOfFRObject
      11.1-4 AsPermutation
      11.1-5 AsTransformation
    11.2 Filters for FRObjects
      11.2-1 IsGroupFRMachine
      11.2-2 IsFRMachineStrRep
      11.2-3 IsMealyMachine
      11.2-4 IsMealyElement
      11.2-5 IsMealyMachineIntRep
      11.2-6 IsMealyMachineDomainRep
      11.2-7 IsVectorFRMachineRep
      11.2-8 IsAlgebraFRMachineRep
      11.2-9 IsLinearFRMachine
      11.2-10 IsLinearFRElement
      11.2-11 IsFRElement
      11.2-12 IsFRObject
      11.2-13 IsFRMachine
      11.2-14 IsInvertible
      11.2-15 IsFRGroup
      11.2-16 IsFRAlgebra
    11.3 Some of the algorithms implemented
      11.3-1 FRMachineRWS
      11.3-2 Order of FR elements
      11.3-3 Membership in semigroups
      11.3-4 Order of groups
      11.3-5 Images and preimages of some groups in f.p. and l.p. groups
      11.3-6 Comparison of FR, Mealy, vector, and algebra elements
      11.3-7 Inverses of linear elements
  12 Miscellanea
    12.1 Helpers
      12.1-1 maybe
      12.1-2 ReturnMaybe
      12.1-3 TensorSum
      12.1-4 TensorProductX
      12.1-5 DirectSum
      12.1-6 PeriodicList
      12.1-7 CompressPeriodicList
      12.1-8 IsConfinal
      12.1-9 ConfinalityClass
      12.1-10 LargestCommonPrefix
      12.1-11 WordGrowth
      12.1-12 ShortGroupRelations
      12.1-13 ShortGroupWordInSet
      12.1-14 SurfaceBraidFpGroup
      12.1-15 CharneyBraidFpGroup
      12.1-16 ArtinRepresentation
      12.1-17 StringByInt
      12.1-18 PositionTower
      12.1-19 CoefficientsInAbelianExtension
      12.1-20 MagmaEndomorphismByImagesNC
      12.1-21 MagmaHomomorphismByImagesNC
      12.1-22 NewFIFO
      12.1-23 ProductIdeal
      12.1-24 DimensionSeries
      12.1-25 Trans
    12.2 User settings
      12.2-1 InfoFR
      12.2-2 FR_SEARCH
  
  
  -------------------------------------------------------