Quelle  group.gd   Sprache: unbekannt

#############################################################################
##
#W group.gd                                                 Laurent Bartholdi
##
##
#Y Copyright (C) 2006, Laurent Bartholdi
##
#############################################################################
##
##  This file declares the (semi)groups of FR and Mealy machines.
##
#############################################################################

#############################################################################
##
#C IsFRGroup . . . . . . . . . . . . . . . . . . . . .all self-similar groups
#C IsFRSemigroup . . . . . . . . . . . . . . . . .all self-similar semigroups
#C IsFRMonoid . . . . . . . . . . . . . . . . . . . .all self-similar monoids
##
## <#GAPDoc Label="IsFRGroup">
## <ManSection>
##   <Filt Name="IsFRGroup" Arg="obj"/>
##   <Filt Name="IsFRMonoid" Arg="obj"/>
##   <Filt Name="IsFRSemigroup" Arg="obj"/>
##   <Returns><K>true</K> if <A>obj</A> is a FR group/monoid/semigroup.</Returns>
##   <Description>
##     These functions accept <E>self-similar groups/monoids/semigroups</E>,
##     i.e. groups/monoids/semigroups whose elements are FR elements.
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareSynonym("IsFRGroup", IsFRElementCollection and IsGroup);
DeclareSynonym("IsFRSemigroup", IsFRElementCollection and IsSemigroup);
DeclareSynonym("IsFRMonoid", IsFRElementCollection and IsMonoid);
#############################################################################

#############################################################################
##
#A AlphabetOfFRSemigroup . . . . . . . . . . . . . . . . alphabet of the tree
##
DeclareAttribute("AlphabetOfFRSemigroup", IsFRSemigroup);
#############################################################################

#############################################################################
##
#F FRGroup
#F FRSemigroup
#F FRMonoid
##
## <#GAPDoc Label="FRGroup">
## <ManSection>
##   <Oper Name="FRGroup" Arg="{definition,}"/>
##   <Oper Name="FRMonoid" Arg="{definition,}"/>
##   <Oper Name="FRSemigroup" Arg="{definition,}"/>
##   <Returns>A new self-similar group/monoid/semigroup.</Returns>
##   <Description>
##     This function constructs a new FR group/monoid/semigroup,
##     generated by group FR elements. It receives as argument any
##     number of strings, each of which represents a generator of
##     the object to be constructed.
##
##     <P/> Each <A>definition</A> is of the form <C>"name=projtrans"</C>,
##     where each of <C>proj</C> and <C>trans</C> is optional.
##     <C>proj</C> is of the form <C><w1,...,wd></C>, where each
##     <C>wi</C> is a (possibly empty) word in the <C>name</C>s or is 1.
##     <C>trans</C> is either a permutation in disjoint cycle notation,
##     or a list, representing the images of a permutation.
##
##     <P/> The last argument may be one of the filters <C>IsMealyElement</C>,
##     <C>IsFRMealyElement</C> or <C>IsFRElement</C>. By default, if each of
##     the states of generators is a generator or 1, the elements of the
##     created object will be Mealy elements; otherwise, they will be
##     FR elements. Specifying such a filter requires them to be in the
##     appropriate category; e.g.,
##     <C>FRGroup("a=(1,2)",IsFRMealyElement)</C> asks for the resulting group
##     to be generated by FR-Mealy elements. The generators must of course be
##     finite-state.
## <Example><![CDATA[
## gap> FRGroup("a=(1,2)","b=(1,2,3,4,5)"); Size(last);
## <self-similar group over [ 1 .. 5 ] with 2 generators>
## 120
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> AssignGeneratorVariables(Dinfinity);
## #I  Assigned the global variables [ a, b ]
## gap> Order(a); Order(b); Order(a*b);
## 2
## 2
## infinity
## gap> ZZ := FRGroup("t=<,t>[2,1]");
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## tau := FRElement([[[b,1],[1]]],[()],[1]);
## <2|f3>
## gap> IsSubgroup(Dinfinity,ZZ);
## false
## gap> IsSubgroup(Dinfinity^tau,ZZ);
## true
## gap> Index(Dinfinity^tau,ZZ);
## 2
## ]]></Example>
## <Example><![CDATA[
## gap> i4 := FRMonoid("s=(1,2)","f=<s,f>[1,1]");
## <self-similar monoid over [ 1 .. 2 ] with 2 generators>
## gap> f := GeneratorsOfMonoid(i4){[1,2]};;
## gap> for i in [1..10] do Add(f,f[i]*f[i+1]); od;
## gap> f[1]^2=One(m);
## true
## gap> f[2]^3=f[2];
## true
## gap> f[11]*f[10]^2=f[1]*Product(f{[5,7..11]})*f[10];
## true
## gap> f[12]*f[11]^2=f[2]*Product(f{[6,8..12]})*f[11];
## true
## ]]></Example>
## <Example><![CDATA[
## gap> i2 := FRSemigroup("f0=<f0,f0>(1,2)","f1=<f1,f0>[2,2]");
## <self-similar semigroup over [ 1 .. 2 ] with 2 generators>
## gap> AssignGeneratorVariables(i2);
## #I  Assigned the global variables [ "f0", "f1" ]
## gap> f0^2=One(i2);
## true
## gap> ForAll([0..10],p->(f0*f1)^p*(f1*f0)^p*f1=f1^2*(f0*f1)^p*(f1*f0)^p*f1);
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="NewSemigroupFRMachine" Arg="..."/>
##   <Attr Name="NewMonoidFRMachine" Arg="..."/>
##   <Attr Name="NewGroupFRMachine" Arg="..."/>
##   <Returns>A new FR machine, based on string descriptions.</Returns>
##   <Description>
##     This command constructs a new FR machine, in a format similar to
##     <Ref Func="FRGroup"/>; namely, the arguments are strings of the form
##     "gen=<word-1,...,word-d>perm"; each <C>word-i</C> is a word in the
##     generators; and <C>perm</C> is a transformation,
##     either written in disjoint cycle or in images notation.
##
##     <P/>Except in the semigroup case, <C>word-i</C> is allowed to be the
##     empty string; and the "<...>" may be skipped altogether.
##     In the group or IMG case, each <C>word-i</C> may also contain inverses.
##         
##     <P/>The following example constructs the "universal Grigorchuk machine".
## <Example><![CDATA[
## gap> m := NewGroupFRMachine("a=(1,2)(3,4)(5,6)","b=<a,b,a,b,,b>",
##      "c=<a,c,,c,a,c>","d=<,d,a,d,a,d>");
## gap> <FR machine with alphabet [ 1, 2, 3, 4, 5, 6 ] on Group( [ a, b, c, d ] )>
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("FRGroup");
DeclareGlobalFunction("FRSemigroup");
DeclareGlobalFunction("FRMonoid");
DeclareGlobalFunction("NewSemigroupFRMachine");
DeclareGlobalFunction("NewMonoidFRMachine");
DeclareGlobalFunction("NewGroupFRMachine");
#############################################################################

#############################################################################
##
#O FRGroupByVirtualEndomorphism
##
## <#GAPDoc Label="FRGroupByVirtualEndomorphism">
## <ManSection>
##   <Oper Name="FRGroupByVirtualEndomorphism" Arg="hom[,transversal]"/>
##   <Returns>A new self-similar group.</Returns>
##   <Description>
##     This function constructs a new FR group <C>P</C>, generated by group FR
##     elements. Its first argument is a virtual endomorphism of a group
##     <C>G</C>, i.e. a homomorphism from a subgroup <C>H</C> to <C>G</C>.
##     The constructed FR group acts on a tree with alphabet a transversal
##     of <C>H</C> in <C>G</C> (represented as <C>[1..d]</C>), and is
##     a homomorphic image of <C>G</C>. The stabilizer of the first-level
##     vertex corresponding to the trivial coset is the image of <C>H</C>.
##     This function is loosely speaking an inverse of
##     <Ref Oper="VirtualEndomorphism"/>.
##
##     <P/> The optional second argument is a transversal of <C>H</C> in
##     <C>G</C>, either of type <C>IsRightTransversal</C> or a list.
##
##     <P/> Furthermore, an option "MealyElement" can be passed to the
##     function, as <C>FRGroupByVirtualEndomorphism(f:MealyElement)</C>,
##     to require the resulting group to be generated by Mealy elements
##     and not FR elements. The call will succeed, of course, only if the
##     representation of <C>G</C> is finite-state.
##
##     <P/> The resulting FR group has an attribute <C>Correspondence(P)</C>
##     that records a homomorphism from <C>G</C> to <C>P</C>.
##
##     <P/> The example below constructs the binary adding machine, and a
##     non-standard representation of it.
## <Example><![CDATA[
## gap> G := FreeGroup(1);
## <free group on the generators [ f1 ]>
## gap> f := GroupHomomorphismByImages(Group(G.1^2),G,[G.1^2],[G.1]);
## [ f1^2 ] -> [ f1 ]
## gap> H := FRGroupByVirtualEndomorphism(f);
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## gap> Display(H.1);
##     |     1      2
## ----+--------+------+
##  x1 | <id>,2   x1,1
## ----+--------+------+
## Initial state: x1
## gap> Correspondence(H);
## [ f1 ] -> [ <2|x1> ]
## gap> H := FRGroupByVirtualEndomorphism(f,[G.1^0,G.1^3]);;
## gap> Display(H.1);
##     |      1        2
## ----+---------+--------+
##  x1 | x1^-1,2   x1^2,1
## ----+---------+--------+
## Initial state: x1
## gap> H := FRGroupByVirtualEndomorphism(f:MealyElement);
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## gap> Display(H.1);
##    |  1     2
## ---+-----+-----+
##  a | b,2   a,1
##  b | b,1   b,2
## ---+-----+-----+
## Initial state: a
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("FRGroupByVirtualEndomorphism",[IsGroupHomomorphism]);
DeclareOperation("FRGroupByVirtualEndomorphism",[IsGroupHomomorphism,IsList]);
#############################################################################

#############################################################################
##
#O VirtualEndomorphism
##
## <#GAPDoc Label="VirtualEndomorphism">
## <ManSection>
##   <Oper Name="VirtualEndomorphism" Arg="g/m,v"/>
##   <Returns>The virtual endomorphism at vertex <A>v</A>.</Returns>
##   <Description>
##     This function returns the homomorphism from <C>Stabilizer(g,v)</C>
##     to <A>g</A>, defined by computing the state at <A>v</A>.
##     It is loosely speaking an inverse of
##     <Ref Oper="FRGroupByVirtualEndomorphism"/>.
##
##     <P/> The first argument <A>m</A> may also be an FR machine.
## <Example><![CDATA[
## gap> A := SCGroup(MealyMachine([[2,1],[2,2]],[(1,2),()]));
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## gap> f := VirtualEndomorphism(A,1);
## MappingByFunction( <self-similar group over [ 1 .. 2 ] with
## 1 generator>, <self-similar group over [ 1 .. 2 ] with
## 1 generator>, function( g ) ... end )
## gap> ((A.1)^2)^f=A.1;
## true
## gap> B := FRGroupByVirtualEndomorphism(f);
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## gap> A=B;
## true
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("VirtualEndomorphism",[IsFRGroup,IsObject]);
#############################################################################

#############################################################################
##
#O SEARCH@
##
## <#GAPDoc Label="SEARCH@">
## <ManSection>
##   <Var Name="SEARCH@"/>
##   <Description>
##     This variable controls the search mechanism in FR groups. It is
##     a record with in particular entries <C>radius</C> and <C>depth</C>.
##
##     <P/> <C>radius</C> limits the search in FR groups to balls of
##     that radius in the generating set. For example, the command
##     <C>x in G</C> will initiate a search in <C>G</C> to attempt to express
##     <C>x</C> as a reasonably short word in the generators of <C>G</C>.
##
##     <P/> <C>depth</C> limits the level of the tree on which quotients
##     of FR groups should be considered. Again for the command <C>x in G</C>,
##     deeper and deeper quotients will be considered, in the hope of finding
##     a quotient of <C>G</C> to which <C>x</C> does not belong.
##
##     <P/> A primitive mechanism is implemented to search alternatively for
##     a quotient disproving <C>x in G</C> and a word proving <C>x in G</C>.
##
##     <P/> When the limits are reached and the search was unsuccessful, an
##     interactive <C>Error()</C> is raised, to let the user increase their
##     values.
##
##     <P/> Specific limits can be passed to any command via the options
##     <C>FRdepth</C> and <C>FRradius</C>, as for example in
##     <C>Size(G:FRdepth:=3,FRradius:=5)</C>.
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
BindGlobal("SEARCH@", rec(depth := 6, volume := 5000));
#############################################################################

#############################################################################
##
#O SCGroup. . . . . . . . . . . . . . . . . . . . . . . . .state-closed group
#O SCSemigroup. . . . . . . . . . . . . . . . . . . . .state-closed semigroup
#O SCMonoid. . . . . . . . . . . . . . . . . . . . . . . .state-closed monoid
##
## <#GAPDoc Label="SCGroup">
## <ManSection>
##   <Oper Name="SCGroup" Arg="m"/>
##   <Oper Name="SCGroupNC" Arg="m"/>
##   <Oper Name="SCMonoid" Arg="m"/>
##   <Oper Name="SCMonoidNC" Arg="m"/>
##   <Oper Name="SCSemigroup" Arg="m"/>
##   <Oper Name="SCSemigroupNC" Arg="m"/>
##   <Returns>The state-closed group/monoid/semigroup generated by the machine <A>m</A>.</Returns>
##   <Description>
##     This function constructs a new FR group/monoid/semigroup <C>g</C>,
##     generated by all the states of the FR machine <A>m</A>.
##     There is a bijective correspondence between
##     <C>GeneratorsOfFRMachine(m)</C> and the generators of <C>g</C>, which
##     is accessible via <C>Correspondence(g)</C>
##     (See <Ref Attr="Correspondence" Label="FR semigroup"/>); it is a
##     homomorphism from the stateset of <A>m</A> to <C>g</C>, or a list
##     indicating for each state of
##     <A>m</A> a corresponding generator index in the generators of <C>g</C>
##     (with negatives for inverses, and 0 for identity).
##
##     <P/> In the non-<C>NC</C> forms, redundant (equal, trivial
##     or mutually inverse) states are removed from the generating set of
##     <C>g</C>.
## <Example><![CDATA[
## gap> b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);; g := SCGroupNC(b);
## <self-similar group over [ 1 .. 2 ] with 3 generators>
## gap> Size(g);
## infinity
## gap> IsOne(Comm(g.2,g.2^g.1));
## true
## ]]></Example>
## <Example><![CDATA[
## gap> i4machine := MealyMachine([[3,3],[1,2],[3,3]],[(1,2),[1,1],()]);
## <Mealy machine on alphabet [ 1, 2 ] with 3 states>
## gap> IsInvertible(i4machine);
## false
## gap> i4 := SCMonoidNC(i4machine);
## <self-similar monoid over [ 1 .. 2 ] with 3 generators>
## gap> f := GeneratorsOfMonoid(i4){[1,2]};;
## gap> for i in [1..10] do Add(f,f[i]*f[i+1]); od;
## gap> f[1]^2=One(m);
## true
## gap> f[2]^3=f[2];
## true
## gap> f[11]*f[10]^2=f[1]*Product(f{[5,7..11]})*f[10];
## true
## gap> f[12]*f[11]^2=f[2]*Product(f{[6,8..12]})*f[11];
## true
## ]]></Example>
## <Example><![CDATA[
## gap> i2machine := MealyMachine([[1,1],[2,1]],[(1,2),[2,2]]);
## <Mealy machine on alphabet [ 1, 2 ] with 2 states>
## gap> i2 := SCSemigroupNC(i2machine);
## <self-similar semigroup over [ 1 .. 2 ] with 2 generators>
## gap> f0 := GeneratorsOfSemigroup(i2)[1];; f1 := GeneratorsOfSemigroup(i2)[2];;
## gap> f0^2=One(i2);
## true
## gap> ForAll([0..10],p->(f0*f1)^p*(f1*f0)^p*f1=f1^2*(f0*f1)^p*(f1*f0)^p*f1);
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="Correspondence" Arg="g" Label="FR semigroup"/>
##   <Returns>A correspondence between the generators of the underlying FR machine of <A>g</A> and <A>g</A>.</Returns>
##   <Description>
##     If <A>g</A> was created as the state closure of an FR machine <C>m</C>,
##     this attribute records the correspondence between <C>m</C> and <A>g</A>.
##
##     <P/> If <C>m</C> is a group/monoid/semigroup/algebra FR machine, then
##     <C>Correspondence(g)</C> is a homomorphism from the stateset of <C>m</C>
##     to <A>g</A>.
##
##     <P/> If <C>m</C> is a Mealy or vector machine, then
##     <C>Correspondence(g)</C> is a list, with in position <M>i</M> the
##     index in the generating set of <A>g</A> of state number <M>i</M>.
##     This index is 0 if there is no corresponding generator because the
##     state is trivial, and is negative if there is no corresponding
##     generator because the inverse of state number <M>i</M> is a
##     generator.
##
##     <P/> See <Ref Oper="SCGroupNC"/>, <Ref Oper="SCGroup"/>,
##     <Ref Oper="SCMonoidNC"/>, <Ref Oper="SCMonoid"/>,
##     <Ref Oper="SCSemigroupNC"/>, <Ref Oper="SCSemigroup"/>,
##     <Ref Oper="SCAlgebraNC"/>, <Ref Oper="SCAlgebra"/>,
##     <Ref Oper="SCAlgebraWithOneNC"/>, and <Ref Oper="SCAlgebraWithOne"/>
##     for examples.
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("SCGroupNC", [IsFRMachine]);
DeclareOperation("SCMonoidNC", [IsFRMachine]);
DeclareOperation("SCSemigroupNC", [IsFRMachine]);
DeclareOperation("SCGroup", [IsFRMachine]);
DeclareOperation("SCMonoid", [IsFRMachine]);
DeclareOperation("SCSemigroup", [IsFRMachine]);
DeclareAttribute("Correspondence", IsFRSemigroup);
#############################################################################

#############################################################################
##
#O  FullSCGroup. . . . . . . . . . . . . . . . . . maximal state-closed group
#O  FullSCMonoid. . . . . . . . . . . . . . . . . maximal state-closed monoid
#O  FullSCSemigroup. . . . . . . . . . . . . . maximal state-closed semigroup
##
## <#GAPDoc Label="FullSCGroup">
## <ManSection>
##   <Func Name="FullSCGroup" Arg="..."/>
##   <Func Name="FullSCMonoid" Arg="..."/>
##   <Func Name="FullSCSemigroup" Arg="..."/>
##   <Returns>A maximal state-closed group/monoid/semigroup on the alphabet <A>a</A>.</Returns>
##   <Description>
##     This function constructs a new FR group, monoid or semigroup, which
##     contains all transformations with given properties of the tree
##     with given alphabet.
##
##     <P/> The arguments can be, in any order: a semigroup, specifying which
##     vertex actions are allowed; a set or domain, specifying the alphabet
##     of the tree; an integer, specifying the maximal depth of elements;
##     and a filter among <Ref Prop="IsFinitaryFRElement"/>,
##     <Ref Prop="IsBoundedFRElement"/>,
##     <Ref Prop="IsPolynomialGrowthFRElement"/> and
##     <Ref Prop="IsFiniteStateFRElement"/>.
##
##     <P/> This object serves as a container for all
##     FR elements with alphabet <A>a</A>. Random elements can be drawn
##     from it; they are Mealy elements with a random number of states, and
##     with the required properties.
## <Example><![CDATA[
## gap> g := FullSCGroup([1..3]);
## FullSCGroup([ 1 .. 3 ]);
## gap> IsSubgroup(g,GuptaSidkiGroup);
## true
## gap> g := FullSCGroup([1..3],Group((1,2,3)));
## FullSCGroup([ 1 .. 3 ], Group( [ (1,2,3) ] ))
## gap> IsSubgroup(g,GuptaSidkiGroup);
## true
## gap> IsSubgroup(g,GrigorchukGroup);
## false
## gap> Random(g);
## <Mealy element on alphabet [ 1, 2, 3 ] with 2 states, initial state 1>
## gap> Size(FullSCGroup([1,2],3));
## 128
## gap> g := FullSCMonoid([1..2]);
## FullSCMonoid([ 1 .. 2 ])
## gap> IsSubset(g,AsTransformation(FullSCGroup([1..2])));
## true
## gap> IsSubset(g,AsTransformation(GrigorchukGroup));
## true
## gap> g := FullSCSemigroup([1..3]);
## FullSCSemigroup([ 1 .. 3 ])
## gap> h := FullSCSemigroup([1..3],Semigroup(Transformation([1,1,1])));
## FullSCSemigroup([ 1 .. 3 ], Semigroup( [ [ 1, 1, 1 ] ] ))
## gap> Size(h);
## 1
## gap> IsSubset(g,h);
## true
## gap> g=FullSCMonoid([1..3]);
## true
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("FullSCGroup");
DeclareGlobalFunction("FullSCSemigroup");
DeclareGlobalFunction("FullSCMonoid");
DeclareAttribute("FullSCFilter", IsFRSemigroup);
DeclareAttribute("FullSCVertex", IsFRSemigroup);
DeclareProperty("HasFullSCData", IsFRSemigroup);
#############################################################################

#############################################################################
##
#O TopVertexTransformations. . the (semi)group acting at the root of the tree
#O VertexTransformations. . . . . . . . . . . . . at all vertices of the tree
##
## <#GAPDoc Label="VertexTransformations">
## <ManSection>
##   <Attr Name="TopVertexTransformations" Arg="g"/>
##   <Returns>The transformations at the root under the action of <A>g</A>.</Returns>
##   <Description>
##     This function returns the permutation group, or the transformation
##     group/semigroup/monoid, of all activities of all elements under the
##     root vertex of the tree on which <A>g</A> acts.
##
##     <P/> It is a synonym for <C>PermGroup(g,1)</C> or
##     <C>TransformationMonoid(g,1)</C> or <C>TransformationSemigroup(g,1)</C>.
## <Example><![CDATA[
## gap> TopVertexTransformations(GrigorchukGroup);
## Group([ (), (1,2) ])
## gap> IsTransitive(last,AlphabetOfFRSemigroup(GrigorchukGroup));
## true
## gap> TopVertexTransformations(FullSCMonoid([1..3]));
## <monoid with 3 generators>
## gap> Size(last);
## 27
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="VertexTransformations" Arg="g" Label="FR semigroup"/>
##   <Returns>The transformations at all vertices under the action of <A>g</A>.</Returns>
##   <Description>
##     This function returns the permutation group, or the transformation
##     group/monoid/semigroup, of all activities of all elements under all
##     vertices of the tree on which <A>g</A> acts.
##
##     <P/> This is the smallest group/monoid/semigroup <C>P</C> such that
##     <A>g</A> is a subset of <C>FullSCGroup(AlphabetOfFRSemigroup(g),P)</C>
##     or <C>FullSCMonoid(AlphabetOfFRSemigroup(g),P)</C> or
##     <C>FullSCSemigroup(AlphabetOfFRSemigroup(g),P)</C>.
## <Example><![CDATA[
## gap> VertexTransformations(GuptaSidkiGroup);
## Group([ (), (1,2,3), (1,3,2) ])
## gap> TopVertexTransformations(Group(GuptaSidkiGroup.2));
## Group(())
## gap> VertexTransformations(Group(GuptaSidkiGroup.2));
## Group([ (), (1,2,3), (1,3,2) ])
## ]]></Example>
##   </Description>
## </ManSection>
##
## <#/GAPDoc>
##
DeclareAttribute("TopVertexTransformations", IsFRSemigroup);
DeclareAttribute("VertexTransformations", IsFRSemigroup);
#############################################################################

#############################################################################
##
#O PermGroup. . . . . . . . . . . . . . . . . .group acting on truncated tree
#O [Epimorphism]PermGroup
#O [Epimorphism]PcGroup
#O [Epimorphism]TransformationMonoid
#O [Epimorphism]TransformationSemigroup
##
## <#GAPDoc Label="PermGroup">
## <ManSection>
##   <Oper Name="PermGroup" Arg="g,l"/>
##   <Oper Name="EpimorphismPermGroup" Arg="g,l"/>
##   <Returns>[An epimorphism to] the permutation group of <A>g</A>'s action on level <A>l</A>.</Returns>
##   <Description>
##     The first function returns a permutation group on <M>d^l</M> points, where
##     <M>d</M> is the size of <A>g</A>'s alphabet. It has as many generators
##     as <A>g</A>, and represents the action of <A>g</A> on the <A>l</A>th
##     layer of the tree.
##
##     <P/> The second function returns a homomorphism from <A>g</A> to
##     this permutation group.
## <Example><![CDATA[
## gap> g := FRGroup("a=(1,2)","b=<a,>"); Size(g);
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## 8
## gap> PermGroup(g,2);
## Group([ (1,3)(2,4), (1,2) ])
## gap> PermGroup(g,3);
## Group([ (1,5)(2,6)(3,7)(4,8), (1,3)(2,4) ])
## gap> List([1..6],i->LogInt(Size(PermGroup(GrigorchukGroup,i)),2));
## [ 1, 3, 7, 12, 22, 42 ]
## gap> g := FRGroup("t=<,t>(1,2)"); Size(g);
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## infinity
## gap> pi := EpimorphismPermGroup(g,5);
## MappingByFunction( <self-similar group over [ 1 .. 2 ] with 1 generator,
## of size infinity>, Group([ (1,17,9,25,5,21,13,29,3,19,11,27,7,23,15,31,
## 2,18,10,26,6,22,14,30,4,20,12,28,8,24,16,32) ]), function( w ) ... end )
## gap> Order(g.1);
## infinity
## gap> Order(g.1^pi);
## 32
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Oper Name="PcGroup" Arg="g,l"/>
##   <Oper Name="EpimorphismPcGroup" Arg="g,l"/>
##   <Returns>[An epimorphism to] the pc group of <A>g</A>'s action on level <A>l</A>.</Returns>
##   <Description>
##     The first function returns a polycyclic group representing the action
##     of <A>g</A> on the <A>l</A>th layer of the tree. It converts the
##     permutation group <C>PermGroup(g,l)</C> to a Pc group, in which
##     computations are often faster.
##
##     <P/> The second function returns a homomorphism from <A>g</A> to
##     this pc group.
## <Example><![CDATA[
## gap> g := PcGroup(GrigorchukGroup,7); time;
## <pc group with 5 generators>
## 3370
## gap> NormalClosure(g,Group(g.3)); time;
## <pc group with 79 generators>
## 240
## gap> g := PermGroup(GrigorchukGroup,7); time;
## <permutation group with 5 generators>
## 3
## gap> NormalClosure(g,Group(g.3)); time;
## <permutation group with 5 generators>
## 5344
## gap> g := FRGroup("t=<,t>(1,2)"); Size(g);
## <self-similar group over [ 1 .. 2 ] with 1 generator>
## infinity
## gap> pi := EpimorphismPcGroup(g,5);
## MappingByFunction( <self-similar group over [ 1 .. 2 ] with
## 1 generator, of size infinity>, Group([ f1, f2, f3, f4, f5 ]), function( w ) ... end )
## gap> Order(g.1);
## infinity
## gap> Order(g.1^pi);
## 32
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Oper Name="TransformationMonoid" Arg="g,l"/>
##   <Oper Name="EpimorphismTransformationMonoid" Arg="g,l"/>
##   <Returns>[An epimorphism to] the transformation monoid of <A>g</A>'s action on level <A>l</A>.</Returns>
##   <Description>
##     The first function returns a transformation monoid on <M>d^l</M> points,
##     where <M>d</M> is the size of <A>g</A>'s alphabet. It has as many
##     generators as <A>g</A>, and represents the action of <A>g</A> on
##     the <A>l</A>th layer of the tree.
##
##     <P/> The second function returns a homomorphism from <A>g</A> to this
##     transformation monoid.
## <Example><![CDATA[
## gap> i4 := SCMonoid(MealyMachine([[3,3],[1,2],[3,3]],[(1,2),[1,1],()]));
## <self-similar monoid over [ 1 .. 2 ] with 3 generators>
## gap> g := TransformationMonoid(i4,6);
## <monoid with 3 generators>
## gap> List([1..6],i->Size(TransformationMonoid(i4,i)));
## [ 4, 14, 50, 170, 570, 1882 ]
## gap> Collected(List(g,RankOfTransformation));
## [ [ 1, 64 ], [ 2, 1280 ], [ 4, 384 ], [ 8, 112 ], [ 16, 32 ], [ 32, 8 ], [ 64, 2 ] ]
## gap> pi := EpimorphismTransformationMonoid(i4,9);
## MappingByFunction( <self-similar monoid over [ 1 .. 2 ] with 3 generators>,
## <monoid with 3 generators>, function( w ) ... end )
## gap> f := GeneratorsOfMonoid(i4){[1,2]};;
## gap> for i in [1..10] do Add(f,f[i]*f[i+1]); od;
## gap> Product(f{[3,5,7,9,11]})=f[11]*f[10];
## false
## gap> Product(f{[3,5,7,9,11]})^pi=(f[11]*f[10])^pi;
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Oper Name="TransformationSemigroup" Arg="g,l"/>
##   <Oper Name="EpimorphismTransformationSemigroup" Arg="g,l"/>
##   <Returns>[An epimorphism to] the transformation semigroup of <A>g</A>'s action on level <A>l</A>.</Returns>
##   <Description>
##     The first function returns a transformation semigroup on <M>d^l</M>
##     points, where <M>d</M> is the size of <A>g</A>'s alphabet.
##     It has as many generators as <A>g</A>, and represents the action
##     of <A>g</A> on the <A>l</A>th layer of the tree.
##
##     <P/> The second function returns a homomorphism from <A>g</A> to this
##     transformation semigroup.
## <Example><![CDATA[
## gap> i2 := SCSemigroup(MealyMachine([[1,1],[2,1]],[(1,2),[2,2]]));
## <self-similar semigroup over [ 1 .. 2 ] with 2 generators>
## gap> g := TransformationSemigroup(i2,6);
## <semigroup with 2 generators>
## gap> List([1..6],i->Size(TransformationSemigroup(i2,i)));
## [ 4, 14, 42, 114, 290, 706 ]
## gap> Collected(List(g,RankOfTransformation));
## [ [ 1, 64 ], [ 2, 384 ], [ 4, 160 ], [ 8, 64 ], [ 16, 24 ], [ 32, 8 ], [ 64, 2 ] ]
## gap> f0 := GeneratorsOfSemigroup(i2)[1];; f1 := GeneratorsOfSemigroup(i2)[2];;
## gap> pi := EpimorphismTransformationSemigroup(i2,10);
## MappingByFunction( <self-similar semigroup over [ 1 .. 2 ] with
## 2 generators>, <semigroup with 2 generators>, function( w ) ... end )
## gap> (f1*(f1*f0)^10)=((f1*f0)^10);
## false
## gap> (f1*(f1*f0)^10)^pi=((f1*f0)^10)^pi;
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Oper Name="EpimorphismGermGroup" Arg="g,l"/>
##   <Oper Name="EpimorphismGermGroup" Arg="g" Label="EGG0"/>
##   <Returns>A homomorphism to a polycyclic group.</Returns>
##   <Description>
##     This function returns an epimorphism to a polycyclic group, encoding
##     the action on the first <A>l</A> levels of the tree and on the germs
##     below. If <A>l</A> is omitted, it is assumed to be <M>0</M>.
##
##     <P/> Since the elements of <A>g</A> are finite automata, they map
##     periodic sequences to periodic sequences. The action on the periods,
##     and in the immediate vicinity of them, is called the <E>germ action</E>
##     of <A>g</A>. This function returns the natural homomorphism from
##     <A>g</A> to the wreath product of this germ group with the quotient of
##     <A>g</A> acting on the <A>l</A>th layer of the tree.
##
##     <P/> The germ group, by default, is abelian. If it is finite, this
##     function returns a homomorphism to a Pc group; otherwise, a
##     homomorphism to a polycyclic group.
##
##     <P/> The <Ref Var="GrigorchukTwistedTwin"/> is, for now, the only example
##     with a hand-coded, non-abelian germ group.
## <Example><![CDATA[
## gap> EpimorphismGermGroup(GrigorchukGroup,0);
## MappingByFunction( GrigorchukGroup, <pc group of size 4 with 2 generators>,
##   function( g ) ... end )
## gap> List(GeneratorsOfGroup(GrigorchukGroup),x->x^last);
## [ <identity> of ..., f1, f1*f2, f2 ]
## gap> StructureDescription(Image(last2));
## "C2 x C2"
## gap> g := FRGroup("t=<,t>(1,2)","m=<,m^-1>(1,2)");;
## gap> EpimorphismGermGroup(g,0);
## MappingByFunction( <state-closed, bounded group over [ 1, 2 ] with 2
##   generators>, Pcp-group with orders [ 0, 0 ], function( x ) ... end )
## gap> EpimorphismGermGroup(g,1);; Range(last); Image(last2);
## Pcp-group with orders [ 2, 0, 0, 0, 0 ]
## Pcp-group with orders [ 2, 0, 0, 0 ]
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="GermData" Arg="group"/>
##   <Oper Name="GermValue" Arg="element, data"/>
##   <Description>
##     The first command computes some data useful to determine the germ
##     value of a group element; the second command computes these germ
##     values. For more information on germs, see <Ref Oper="Germs"/>.
## <Example><![CDATA[
## gap> data := GermData(GrigorchukGroup);
## rec( endo := [ f1, f2 ] -> [ f1*f2, f1 ], group := <pc group of size 4 with 2 generators>,
##   machines := [  ], map := [ <identity> of ..., f2, f1, f1*f2, <identity> of ... ],
##   nucleus := [ <Trivial Mealy element on alphabet [ 1 .. 2 ]>, d, c, b, a ],
##   nucleusmachine := <Mealy machine on alphabet [ 1 .. 2 ] with 5 states> )
## gap> List(GeneratorsOfGroup(GrigorchukGroup),x->GermValue(x,data));
## [ <identity> of ..., f1*f2, f1, f2 ]
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute("LevelOfEpimorphismFromFRGroup",IsGroupHomomorphism);
DeclareOperation("PermGroup", [IsFRGroup, IsInt]);
DeclareOperation("EpimorphismPermGroup", [IsFRGroup, IsInt]);
DeclareOperation("PcGroup", [IsFRGroup, IsInt]);
DeclareOperation("EpimorphismPcGroup", [IsFRGroup, IsInt]);
DeclareOperation("TransformationMonoid", [IsFRMonoid, IsInt]);
DeclareOperation("EpimorphismTransformationMonoid", [IsFRMonoid, IsInt]);
DeclareOperation("TransformationSemigroup", [IsFRSemigroup, IsInt]);
DeclareOperation("EpimorphismTransformationSemigroup", [IsFRSemigroup, IsInt]);
DeclareOperation("EpimorphismGermGroup",[IsFRGroup, IsInt]);
DeclareOperation("EpimorphismGermGroup",[IsFRGroup]);
#############################################################################

#############################################################################
##
#P IsStateClosed. . . . . . . . . . . . are all states of elements of G in G?
#O StateClosure. . . . . . . . . the smallest state-closed group containing G
#P IsRecurrent. . . . . . . . .do all elements appear under any fixed vertex?
#P IsLevelTransitive. . . . . . is there one orbit at each level of the tree?
##
## <#GAPDoc Label="IsStateClosed">
## <ManSection>
##   <Prop Name="IsStateClosed" Arg="g"/>
##   <Returns><K>true</K> if all states of elements of <A>g</A> belong to <A>g</A>.</Returns>
##   <Description>
##     This function tests whether <A>g</A> is a <E>state-closed</E> group,
##     i.e. a group such that all states of all elements of <A>g</A> belong
##     to <A>g</A>.
##
##     <P/> The smallest state-closed group containing <A>g</A> is computed
##     with <Ref Oper="StateClosure"/>.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> AssignGeneratorVariables(Dinfinity);
## #I  Assigned the global variables [ a, b ]
## gap> IsStateClosed(Group(a));
##      IsStateClosed(Group(b));
##      IsStateClosed(Dinfinity);
## true
## false
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Oper Name="StateClosure" Arg="g"/>
##   <Returns>The smallest state-closed group containing <A>g</A>.</Returns>
##   <Description>
##     This function computes the smallest group containing all states of
##     all elements of <A>g</A>, i.e. the smallest group containing <A>g</A>
##     and for which <Ref Prop="IsStateClosed"/> returns <K>true</K>.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> AssignGeneratorVariables(Dinfinity);
## #I  Assigned the global variables [ a, b ]
## gap> StateStateClosure(Group(a))=Dinfinity; StateClosure(Group(b))=Dinfinity;
## false
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="IsRecurrentFRSemigroup" Arg="g"/>
##   <Returns><K>true</K> if <A>g</A> is a recurrent group.</Returns>
##   <Description>
##     This function returns <K>true</K> if <A>g</A> is a <E>recurrent</E>
##     group, i.e. if, for every vertex <C>v</C>, all elements of <A>g</A>
##     appear as states at <C>v</C> of elements fixing <C>v</C>.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> AssignGeneratorVariables(Dinfinity);
## #I  Assigned the global variables [ a, b ]
## gap> IsRecurrentFRSemigroup(Group(a)); IsRecurrentFRSemigroup(Group(b));
## false
## false
## gap> IsRecurrentFRSemigroup(Dinfinity);
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="IsLevelTransitiveFRGroup" Arg="g"/>
##   <Returns><K>true</K> if <A>g</A> is a level-transitive group.</Returns>
##   <Description>
##     This function returns <K>true</K> if <A>g</A> is a
##     <E>level-transitive</E> group, i.e. if the action of <A>g</A> is
##     transitive at every level of the tree on which it acts.
##
##     <P/> This function can be abbreviated as <C>IsLevelTransitive</C>.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> AssignGeneratorVariables(Dinfinity);
## #I  Assigned the global variables [ a, b ]
## gap> IsLevelTransitiveFRGroup(Group(a)); IsLevelTransitiveFRGroup(Group(b));
##      IsLevelTransitiveFRGroup(Dinfinity);
## false
## false
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="IsInfinitelyTransitive" Arg="g"/>
##   <Prop Name="IsLevelTransitiveOnPatterns" Arg="g"/>
##   <Returns><K>true</K> if <A>g</A> is infinitely transitive.</Returns>
##   <Description>
##     This function returns <K>true</K> if <A>g</A> is an
##     <E>infinitely transitive</E> group. This means that <A>g</A> is
##     the state-closed group of a bireversible Mealy machine (see <Ref
##     Prop="IsBireversible"/>), and that
##     the action of the set of reduced words of any given length over the
##     alphabet (where "reduced" means no successive letters related by
##     the involution) is transitive.
##
##     <P/> Reduced words are defined as follows: if the underlying Mealy
##     machine of <A>g</A> has an involution on its alphabet
##     (see <Ref Attr="AlphabetInvolution"/>), then reduced words are words
##     in which two consecutive letters are not images of each other under
##     the involution. If no involution is defined, then all words are
##     considered reduced; the command then becomes synonymous to
##     <Ref Prop="IsLevelTransitiveFRGroup"/>.
##
##     <P/> This notion is of fundamental importance for the study of
##     lattices in a product of trees; it implies under appropriate
##     circumstances that the dual group is free.
## <Example><![CDATA[
## gap> IsInfinitelyTransitive(BabyAleshinGroup);
## true
## gap> IsLevelTransitiveFRGroup(BabyAleshinGroup);
## true
## gap> s := DualMachine(BabyAleshinMachine);
## <Mealy machine on alphabet [ 1 .. 3 ] with 2 states>
## gap> AlphabetInvolution(s); # set attribute
## [ 1, 2, 3 ]
## gap> g := SCGroup(s);
## <state-closed group over [ 1 .. 3 ] with 2 generators>
## gap> IsInfinitelyTransitive(g);
## true
## gap> IsLevelTransitiveFRGroup(g);
## false
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty("IsStateClosed", IsFRSemigroup);
DeclareOperation("StateClosure", [IsFRSemigroup]);
DeclareProperty("IsRecurrentFRSemigroup", IsFRSemigroup);
DeclareProperty("IsLevelTransitiveFRGroup", IsFRSemigroup);
DeclareProperty("IsInfinitelyTransitive", IsFRGroup);
DeclareProperty("IsLevelTransitiveOnPatterns", IsFRGroup);
#############################################################################

#############################################################################
##
#P IsContracting
#A NucleusOfFRSemigroup
#A NucleusMachine
##
## <#GAPDoc Label="IsContracting">
## <ManSection>
##   <Prop Name="IsContracting" Arg="g"/>
##   <Returns><K>true</K> if <A>g</A> is a contracting semigroup.</Returns>
##   <Description>
##     This function returns <K>true</K> if <A>g</A> is a <E>contracting</E>
##     semigroup, i.e. if there exists a finite subset <C>N</C> of <A>g</A>
##     such that the <Ref Oper="LimitStates"/> of every element of <A>g</A>
##     belong to <C>N</C>.
##
##     <P/> The minimal such <C>N</C> can be computed with <Ref Attr="NucleusOfFRSemigroup"/>.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> IsContracting(Dinfinity);
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="NucleusOfFRSemigroup" Arg="g"/>
##   <Oper Name="Nucleus" Arg="g" Label="FR semigroup"/>
##   <Returns>The nucleus of the contracting semigroup <A>g</A>.</Returns>
##   <Description>
##     This function returns the <E>nucleus</E> of the contracting semigroup
##     <A>g</A>, i.e. the smallest subset <C>N</C> of <A>g</A>
##     such that the <Ref Oper="LimitStates"/> of every element of <A>g</A>
##     belong to <C>N</C>.
##
##     <P/> This function returns <K>fail</K> if no such <C>N</C> exists.
##     Usually, it loops forever without being able to decide whether <C>N</C>
##     is finite or infinite. It succeeds precisely when
##     <C>IsContracting(g)</C> succeeds.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> NucleusOfFRSemigroup(Dinfinity);
## [ <2|identity ...>, <2|b>, <2|a> ]
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="NucleusMachine" Arg="g" Label="FR semigroup"/>
##   <Returns>The nucleus machine of the contracting semigroup <A>g</A>.</Returns>
##   <Description>
##     This function returns the <E>nucleus</E> of the contracting semigroup
##     <A>g</A>, see <Ref Attr="NucleusOfFRSemigroup"/>, in the form of a Mealy machine.
##
##     <P/> Since all states of the nucleus are elements of the nucleus, the
##     transition and output function may be restricted to the nucleus,
##     defining a Mealy machine. Finitely generated recurrent groups are
##     generated by their nucleus machine.
##
##     <P/> This function returns <K>fail</K> if no such <C>n</C> exists.
##     Usually, it loops forever without being able to decide whether <C>n</C>
##     is finite or infinite. It succeeds precisely when
##     <C>IsContracting(g)</C> succeeds.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> M := NucleusMachine(Dinfinity);
## <Mealy machine on alphabet [ 1, 2 ] with 3 states>
## gap> Display(M);
##    |  1     2
## ---+-----+-----+
##  a | a,1   a,2
##  b | c,1   b,2
##  c | a,2   a,1
## ---+-----+-----+
## gap> Dinfinity=SCGroup(M);
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="AdjacencyBasesWithOne" Arg="g"/>
##   <Attr Name="AdjacencyPoset" Arg="g"/>
##   <Returns>The bases, or the poset, of the simplicial model of <A>g</A>.</Returns>
##   <Description>
##     For these arguments, <A>g</A> can be either the nucleus of an FR
##     semigroup, or that semigroup itself, in which case its nucleus is
##     first computed.
##
##     <P/> The first function computes those maximal (for inclusion)
##     subsets of the nucleus that are recurrent, namely subsets <C>B</C>
##     such that <C>Set(B,x->States(x,v))=B</C> for a string <C>v</C>.
##
##     <P/> The second function then computes the poset of intersections of
##     these bases, and returns it as a binary relation.
##
##     <P/> For more details on these concepts, see <Cite Key="0810.4936"/>.
## <Example><![CDATA[
## gap> n := NucleusOfFRSemigroup(BasilicaGroup);
## [ <Trivial Mealy element on alphabet [ 1 .. 2 ]>, b,
##   <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
##   <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
##   <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
##   <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
##   <Mealy element on alphabet [ 1 .. 2 ] with 3 states> ]
## gap> AdjacencyBasesWithOne(n);
## [ [ <Trivial Mealy element on alphabet [ 1 .. 2 ]>,
##       <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
##       <Mealy element on alphabet [ 1 .. 2 ] with 3 states> ],
##   [ <Trivial Mealy element on alphabet [ 1 .. 2 ]>,
##       <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
##       <Mealy element on alphabet [ 1 .. 2 ] with 3 states> ],
##   [ <Trivial Mealy element on alphabet [ 1 .. 2 ]>,
##       <Mealy element on alphabet [ 1 .. 2 ] with 3 states>,
##       <Mealy element on alphabet [ 1 .. 2 ] with 3 states> ] ]
## gap> AdjacencyPoset(n);
## <general mapping: <object> -> <object> >
## gap> Draw(HasseDiagramBinaryRelation(last));
## ]]></Example>
##     This produces (in a new window) the following picture:
##     <Alt Only="LaTeX"><![CDATA[
##       \includegraphics[height=3cm,keepaspectratio=true]{hasse.jpg}
##     ]]></Alt>
##     <Alt Only="HTML"><![CDATA[
##       <img alt="Hasse Diagram" src="hasse.jpg">
##     ]]></Alt>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty("IsContracting", IsFRSemigroup);
DeclareAttribute("NucleusOfFRSemigroup", IsFRSemigroup);
DeclareAttribute("NucleusMachine", IsFRSemigroup);
DeclareAttribute("AdjacencyBasesWithOne", IsFRElementCollection);
DeclareAttribute("AdjacencyPoset", IsFRElementCollection);
#############################################################################

#############################################################################
##
#P IsFinitary
#P IsBounded
#P IsFiniteState
##
## <#GAPDoc Label="IsFinitary">
## <ManSection>
##   <Prop Name="IsFinitaryFRSemigroup" Arg="g"/>
##   <Prop Name="IsWeaklyFinitaryFRSemigroup" Arg="g"/>
##   <Prop Name="IsBoundedFRSemigroup" Arg="g"/>
##   <Prop Name="IsPolynomialGrowthFRSemigroup" Arg="g"/>
##   <Prop Name="IsFiniteStateFRSemigroup" Arg="g"/>
##   <Returns><K>true</K> if all elements of <A>g</A> have the required property.</Returns>
##   <Description>
##     This function returns <K>true</K> if all elements of <A>g</A>
##     have the required property, as FR elements; see
##     <Ref Prop="IsFinitaryFRElement"/>,
##     <Ref Prop="IsWeaklyFinitaryFRElement"/>,
##     <Ref Prop="IsBoundedFRElement"/>,
##     <Ref Prop="IsPolynomialGrowthFRElement"/> and
##     <Ref Prop="IsFiniteStateFRElement"/>.
## <Example><![CDATA[
## gap> G := FRGroup("a=(1,2)","b=<a,b>","c=<c,b>","d=<d,d>(1,2)");
## <self-similar group over [ 1 .. 2 ] with 4 generators>
## gap> L := [Group(G.1),Group(G.1,G.2),Group(G.1,G.2,G.3),G];;
## gap> List(L,IsFinitaryFRSemigroup);
## [ true, false, false, false ]
## gap> List(L,IsBoundedFRSemigroup);
## [ true, true, false, false ]
## gap> List(L,IsPolynomialGrowthFRSemigroup);
## [ true, true, true, false ]
## gap> List(L,IsFiniteStateFRSemigroup);
## [ true, true, true, true ]
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="Degree" Arg="g" Label="FR semigroup"/>
##   <Attr Name="DegreeOfFRSemigroup" Arg="g"/>
##   <Attr Name="Depth" Arg="g" Label="FR semigroup"/>
##   <Attr Name="DepthOfFRSemigroup" Arg="g"/>
##   <Returns>The maximal degree/depth of elements of <A>g</A>.</Returns>
##   <Description>
##     This function returns the maximal degree/depth of elements of <A>g</A>;
##     see <Ref Attr="Degree" Label="FR element"/> and
##     <Ref Attr="Depth" Label="FR element"/>.
## <Example><![CDATA[
## gap> G := FRGroup("a=(1,2)","b=<a,b>","c=<c,b>");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> Degree(Group(G.1)); Degree(Group(G.1,G.2)); Degree(G);
## 0
## 1
## 2
## gap> Depth(Group(G.1)); Depth(Group(G.1,G.2)); Depth(G);
## 1
## infinity
## infinity
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="HasOpenSetConditionFRSemigroup" Arg="g"/>
##   <Returns><K>true</K> if <A>g</A> has the open set condition.</Returns>
##   <Description>
##     This function returns <K>true</K> if all elements of <A>g</A>
##     have the <E>open set condition</E>, see
##     <Ref Prop="HasOpenSetConditionFRElement"/>.
## <Example><![CDATA[
## gap> HasOpenSetConditionFRSemigroup(GrigorchukGroup);
## false
## gap> HasOpenSetConditionFRSemigroup(BinaryAddingGroup);
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="HasCongruenceProperty" Arg="G"/>
##   <Returns><K>true</K> if <A>G</A> has the congruence property.</Returns>
##   <Description>
##     This function returns <K>true</K> if the transformation
##     (semi)group <A>G</A> has the <E>congruence property</E>, namely if
##     every homomorphism <M>G\to Q</M> to a finite quotient factors as
##     <M>G\to H\to Q</M> via an action of <M>G</M> on a finite set.
##
##     <P/> This command is not guaranteed to terminate.
## <Example><![CDATA[
## gap> HasCongruenceProperty(GrigorchukGroup);
## true
## gap> HasCongruenceProperty(GrigorchukTwistedTwin);
## ...runs forever...
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty("IsFinitaryFRSemigroup", IsFRSemigroup);
DeclareProperty("IsWeaklyFinitaryFRSemigroup", IsFRSemigroup);
DeclareProperty("IsBoundedFRSemigroup", IsFRSemigroup);
DeclareProperty("IsPolynomialGrowthFRSemigroup", IsFRSemigroup);
DeclareProperty("IsFiniteStateFRSemigroup", IsFRSemigroup);
DeclareAttribute("DegreeOfFRSemigroup", IsFRSemigroup);
DeclareAttribute("DepthOfFRSemigroup", IsFRSemigroup);
DeclareProperty("HasOpenSetConditionFRSemigroup", IsFRSemigroup);
DeclareOperation("Depth", [IsFRSemigroup]);
DeclareAttribute("GermData", IsFRGroup, "mutable");
DeclareOperation("GermValue", [IsFRElement, IsRecord]);
DeclareProperty("HasCongruenceProperty", IsFRGroup);
#############################################################################

#############################################################################
##
#P IsTorsionGroup ...
##
## <#GAPDoc Label="IsTorsionGroup">
## <ManSection>
##   <Prop Name="IsTorsionGroup" Arg="g"/>
##   <Returns><K>true</K> if <A>g</A> is a torsion group.</Returns>
##   <Description>
##     This function returns <K>true</K> if <A>g</A> is a torsion group,
##     i.e. if every element in <A>g</A> has finite order; and <K>false</K>
##     if <A>g</A> contains an element of infinite order.
##
##     <P/> This method is quite rudimentary, and is not guaranteed to
##     terminate. At the minimum, <A>g</A> should be a group in which
##     <C>Order()</C> succeeds in computing element orders; e.g. a
##     bounded group in Mealy machine format.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>":IsMealyElement);
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> IsTorsionGroup(Dinfinity);
## false
## gap> IsTorsionGroup(GrigorchukGroup); IsTorsionGroup(GuptaSidkiGroup);
## true
## true
## gap> IsTorsionGroup(FabrykowskiGuptaGroup);
## false
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="IsTorsionFreeGroup" Arg="g"/>
##   <Returns><K>true</K> if <A>g</A> is a torsion-free group.</Returns>
##   <Description>
##     This function returns <K>true</K> if <A>g</A> is a torsion-free group,
##     i.e. if no element in <A>g</A> has finite order; and <K>false</K>
##     if <A>g</A> contains an element of finite order.
##
##     <P/> This method is quite rudimentary, and is not guaranteed to
##     terminate. At the minimum, <A>g</A> should be a group in which
##     <C>Order()</C> succeeds in computing element orders; e.g. a
##     bounded group in Mealy machine format.
## <Example><![CDATA[
## gap> Dinfinity := FRGroup("a=(1,2)","b=<a,b>":IsMealyElement);
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> IsTorsionFreeGroup(Dinfinity);
## false
## gap> IsTorsionFreeGroup(BasilicaGroup);
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="IsAmenableGroup" Arg="g"/>
##   <Returns><K>true</K> if <A>g</A> is an amenable group.</Returns>
##   <Description>
##     Amenable groups, introduced by von Neumann <Cite Key="vneumann"/>,
##     are those groups that admit a finitely additive,
##     translation-invariant measure.
## <Example><![CDATA[
## gap> IsAmenableGroup(FreeGroup(2));
## false
## gap> IsAmenableGroup(BasilicaGroup);
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="IsVirtuallySimpleGroup" Arg="g"/>
##   <Attr Name="LambdaElementVHGroup" Arg="g"/>
##   <Returns><K>true</K> if <A>g</A> admits a finite-index simple subgroup.</Returns>
##   <Description>
##     This function attempts to prove that the VH group <A>g</A> admits a finite-index
##     simple subgroup.
##
##     <P/> It is based on the following test: let <C>D</C> be a direction
##     (vertical or horizontal) such that the corresponding action is
##     infinitely transitive (see <Ref Prop="IsInfinitelyTransitive"/>). If the corresponding
##     subgroup of <A>g</A> contains a non-trivial element <M>\lambda</M> that acts
##     trivially in the corresponding action, then every normal subgroup contains
##     <M>\lambda</M>. It then remains to check that the normal closure of <M>\lambda</M>
##     has finite index. This element <M>\lambda</M> is then stored as the
##     attribute <C>LambdaElementVHGroup(g)</C>.
##
##     <P/> The current implementation is based on results in
##     <Cite Key="MR1839488"/> and <Cite Key="MR1839489"/>, and does not
##     work for the Rattaggi examples (see <Ref Var="RattaggiGroup"/>).
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="IsResiduallyFinite" Arg="obj"/>
##   <Returns><K>true</K> if <A>obj</A> is residually finite.</Returns>
##   <Description>
##     An object is <E>residually finite</E> if it can be approximated
##     arbitrarily well by finite quotients; i.e. if for every
##     <M>g\neq h\in X</M> there exists a finite quotient <M>\pi:X\to Q</M>
##     such that <M>g^\pi\neq h^\pi</M>.
## <Example><![CDATA[
## gap> IsResiduallyFinite(FreeGroup(2));
## true
## gap> IsResiduallyFinite(BasilicaGroup);
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="IsSQUniversal" Arg="obj"/>
##   <Returns><K>true</K> if <A>obj</A> is SQ-universal.</Returns>
##   <Description>
##     An object <A>obj</A> is <E>SQ-universal</E> if every countable
##     object of the same category as <A>obj</A> is a subobject of a
##     quotient of <A>obj</A>.
## <Example><![CDATA[
## gap> IsSQUniversal(FreeGroup(2));
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="IsJustInfinite" Arg="obj"/>
##   <Returns><K>true</K> if <A>obj</A> is just-infinite.</Returns>
##   <Description>
##     An object <A>obj</A> is <E>just-infinite</E> if <A>obj</A> is
##     infinite, but every quotient of <A>obj</A> is finite.
## <Example><![CDATA[
## gap> IsJustInfinite(FreeGroup(2));
## false
## gap> IsJustInfinite(FreeGroup(1));
## true
## gap> IsJustInfinite(GrigorchukGroup); time
## true
## 8284
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareProperty("IsTorsionGroup", IsGroup);
DeclareSynonym("IsTorsionFreeGroup", IsTorsionFree);
DeclareProperty("IsAmenableGroup", IsGroup);
DeclareProperty("IsVirtuallySimpleGroup",IsGroup);
DeclareProperty("IsSQUniversal",IsObject);
DeclareProperty("IsJustInfinite",IsObject);
DeclareProperty("IsResiduallyFinite",IsObject);
#############################################################################

#############################################################################
##
#P IsomorphismFRGroup(G)
#P IsomorphismMealyGroup(G)
##
## <#GAPDoc Label="IsomorphismFRGroup">
## <ManSection>
##   <Oper Name="FRMachineFRGroup" Arg="g"/>
##   <Oper Name="FRMachineFRMonoid" Arg="g"/>
##   <Oper Name="FRMachineFRSemigroup" Arg="g"/>
##   <Oper Name="MealyMachineFRGroup" Arg="g"/>
##   <Oper Name="MealyMachineFRMonoid" Arg="g"/>
##   <Oper Name="MealyMachineFRSemigroup" Arg="g"/>
##   <Returns>A machine describing all generators of <A>g</A>.</Returns>
##   <Description>
##     This function constructs a new group/monoid/semigroup/Mealy FR machine,
##     with (at least) one generator per generator of <A>g</A>.
##     This is done by adding all machines of all generators of <A>g</A>,
##     and minimizing.
##
##     <P/> In particular, if <A>g</A> is state-closed, then
##     <C>SCGroup(FRMachineFRGroup(g))</C> gives a group isomorphic to
##     <A>g</A>, and similarly for monoids and semigroups.
## <Example><![CDATA[
## gap> FRMachineFRGroup(GuptaSidkiGroup);
## <FR machine with alphabet [ 1 .. 3 ] on Group( [ f11, f12 ] )>
## gap> Display(last);
##  G   |     1          2        3
## -----+--------+----------+--------+
##  f11 | <id>,2     <id>,3   <id>,1
##  f12 |  f11,1   f11^-1,2    f12,3
## -----+--------+----------+--------+
## ]]></Example>
## <Example><![CDATA[
## gap> FRMachineFRMonoid(I4Monoid);
## <FR machine with alphabet [ 1 .. 2 ] on Monoid( [ m11, m12 ], ... )>
## gap> Display(last);
##  M   |     1        2
## -----+--------+--------+
##  m11 | <id>,2   <id>,1
##  m12 |  m11,1    m12,1
## -----+--------+--------+
## ]]></Example>
## <Example><![CDATA[
## gap> FRMachineFRSemigroup(I2Monoid);
## <FR machine with alphabet [ 1 .. 2 ] on Semigroup( [ s11, s12, s1 ] )>
## gap> Display(last);
##  S   |    1       2
## -----+-------+-------+
##  s11 | s11,1   s11,2
##  s12 | s12,2   s12,1
##   s1 |  s1,2   s12,2
## -----+-------+-------+
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Oper Name="IsomorphismFRGroup" Arg="g"/>
##   <Oper Name="IsomorphismFRMonoid" Arg="g"/>
##   <Oper Name="IsomorphismFRSemigroup" Arg="g"/>
##   <Returns>An isomorphism towards a group/monoid/semigroup on a single FR machine.</Returns>
##   <Description>
##     This function constructs a new FR group/monoid/semigroup, such that
##     all elements of the resulting object have the same underlying
##     group/monoid/semigroup FR machine.
## <Example><![CDATA[
## gap> phi := IsomorphismFRGroup(GuptaSidkiGroup);
## [ <Mealy element on alphabet [ 1, 2, 3 ] with 2 states, initial state 1>,
##   <Mealy element on alphabet [ 1, 2, 3 ] with 4 states, initial state 1> ] ->
## [ <3|identity ...>, <3|f1>, <3|f1^-1>, <3|f2> ]
## gap> Display(GuptaSidkiGroup.2);
##    |  1     2     3
## ---+-----+-----+-----+
##  a | a,1   a,2   a,3
##  b | a,2   a,3   a,1
##  c | a,3   a,1   a,2
##  d | b,1   c,2   d,3
## ---+-----+-----+-----+
## Initial state: d
## gap> Display(GuptaSidkiGroup.2^phi);
##     |     1         2        3
## ----+--------+---------+--------+
##  f1 | <id>,2    <id>,3   <id>,1
##  f2 |   f1,1   f1^-1,2     f2,3
## ----+--------+---------+--------+
## Initial state: f2
## ]]></Example>
## <Example><![CDATA[
## gap> phi := IsomorphismFRSemigroup(I2Monoid);
## MappingByFunction( I2, <self-similar semigroup over [ 1 .. 2 ] with
## 3 generators>, <Operation "AsSemigroupFRElement"> )
## gap> Display(GeneratorsOfSemigroup(I2Monoid)[3]);
##    |  1     2
## ---+-----+-----+
##  a | a,2   b,2
##  b | b,2   b,1
## ---+-----+-----+
## Initial state: a
## gap> Display(GeneratorsOfSemigroup(I2Monoid)[3]^phi);
##  S  |   1      2
## ----+------+------+
##  s1 | s1,2   s2,2
##  s2 | s2,2   s2,1
## ----+------+------+
## Initial state: s1
## ]]></Example>
## <Example><![CDATA[
## gap> phi := IsomorphismFRMonoid(I4Monoid);
## MappingByFunction( I4, <self-similar monoid over [ 1 .. 2 ] with
## 2 generators>, <Operation "AsMonoidFRElement"> )
## gap> Display(GeneratorsOfMonoid(I4Monoid)[1]);
##    |  1     2
## ---+-----+-----+
##  a | b,2   b,1
##  b | b,1   b,2
## ---+-----+-----+
## Initial state: a
## gap> Display(GeneratorsOfMonoid(I4Monoid)[1]^phi);
##  M  |     1        2
## ----+--------+--------+
##  m1 | <id>,2   <id>,1
## ----+--------+--------+
## Initial state: m1
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Oper Name="IsomorphismMealyGroup" Arg="g"/>
##   <Oper Name="IsomorphismMealyMonoid" Arg="g"/>
##   <Oper Name="IsomorphismMealySemigroup" Arg="g"/>
##   <Returns>An isomorphism towards a group/monoid/semigroup all of whose elements are Mealy machines.</Returns>
##   <Description>
##     This function constructs a new FR group/monoid/semigroup, such that
##     all elements of the resulting object are Mealy machines.
## <Example><![CDATA[
## gap> G := FRGroup("a=(1,2)","b=<a,b>","c=<c,b>");
## <self-similar group over [ 1 .. 2 ] with 3 generators>
## gap> phi := IsomorphismMealyGroup(G);
## [ <2|a>, <2|b>, <2|c> ] ->
## [ <Mealy element on alphabet [ 1, 2 ] with 2 states, initial state 1>,
##   <Mealy element on alphabet [ 1, 2 ] with 3 states, initial state 1>,
##   <Mealy element on alphabet [ 1, 2 ] with 4 states, initial state 1> ]
## gap> Display(G.3);
##    |     1        2
## ---+--------+--------+
##  a | <id>,2   <id>,1
##  b |    a,1      b,2
##  c |    c,1      b,2
## ---+--------+--------+
## Initial state: c
## gap> Display(G.3^phi);
##    |  1     2
## ---+-----+-----+
##  a | a,1   b,2
##  b | c,1   b,2
##  c | d,2   d,1
##  d | d,1   d,2
## ---+-----+-----+
## Initial state: a
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("FRMachineFRGroup", [IsFRGroup]);
DeclareOperation("FRMachineFRMonoid", [IsFRMonoid]);
DeclareOperation("FRMachineFRSemigroup", [IsFRSemigroup]);
DeclareOperation("MealyMachineFRGroup", [IsFRGroup]);
DeclareOperation("MealyMachineFRMonoid", [IsFRMonoid]);
DeclareOperation("MealyMachineFRSemigroup", [IsFRSemigroup]);
DeclareOperation("IsomorphismFRGroup", [IsFRGroup]);
DeclareOperation("IsomorphismFRMonoid", [IsFRMonoid]);
DeclareOperation("IsomorphismFRSemigroup", [IsFRSemigroup]);
DeclareOperation("IsomorphismMealyGroup", [IsFRGroup]);
DeclareOperation("IsomorphismMealyMonoid", [IsFRMonoid]);
DeclareOperation("IsomorphismMealySemigroup", [IsFRSemigroup]);
#############################################################################

#############################################################################
##
#O StabilizerImage
##
## <#GAPDoc Label="StabilizerImage">
## <ManSection>
##   <Oper Name="StabilizerImage" Arg="g,v"/>
##   <Returns>The group of all states at <A>v</A> of elements of <A>g</A> fixing <A>v</A>.</Returns>
##   <Description>
##     This function constructs a new FR group, consisting of all states at
##     vertex <A>v</A> (which can be an integer or a list) of the stabilizer
##     of <A>v</A> in <A>g</A>.
##
##     <P/> The result is <A>g</A> itself precisely if <A>g</A> is recurrent
##     (see <Ref Prop="IsRecurrentFRSemigroup"/>).
## <Example><![CDATA[
## gap> G := FRGroup("t=<,t>(1,2)","u=<,u^-1>(1,2)","b=<u,t>");
## <self-similar group over [ 1 .. 2 ] with 3 generators>
## gap> Stabilizer(G,1);
## <self-similar group over [ 1 .. 2 ] with 5 generators>
## gap> GeneratorsOfGroup(last);
## [ <2|u*t^-1>, <2|b>, <2|t^2>, <2|t*u>, <2|t*b*t^-1> ]
## gap> StabilizerImage(G,1);
## <self-similar group over [ 1 .. 2 ] with 5 generators>
## gap> GeneratorsOfGroup(last);
## [ <2|identity ...>, <2|u>, <2|t>, <2|u^-1>, <2|t> ]
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Oper Name="LevelStabilizer" Arg="g,n"/>
##   <Returns>The fixator of the <A>n</A>th level of the tree.</Returns>
##   <Description>
##     This function constructs the normal subgroup of <A>g</A> that fixes
##     the <A>n</A>th level of the tree.
## <Example><![CDATA[
## gap> G := FRGroup("t=<,t>(1,2)","a=(1,2)");
## <self-similar group over [ 1 .. 2 ] with 2 generators>
## gap> LevelStabilizer(G,2);
## <self-similar group over [ 1 .. 2 ] with 9 generators>
## gap> Index(G,last);
## 8
## gap> IsNormal(G,last2);
## true
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("StabilizerImage", [IsFRSemigroup, IsObject]);
DeclareOperation("LevelStabilizer", [IsFRSemigroup, IsInt]);
#############################################################################

#############################################################################
##
#O TreeWreathProduct
##
## <#GAPDoc Label="Products">
## <ManSection>
##   <Oper Name="TreeWreathProduct" Arg="g,h,x0,y0" Label="FR group"/>
##   <Returns>The tree-wreath product of groups <A>g,h</A>.</Returns>
##   <Description>
##     The tree-wreath product of two FR groups is a group generated by
##     a copy of <A>g</A> and of <A>h</A>, in such a way that many
##     conjugates of <A>g</A> commute.
##
##     <P/> More formally, assume without loss of generality that all
##     generators of <A>g</A> are states of a machine <C>m</C>, and that
##     all generators of <A>h</A> are states of a machine <C>n</C>. Then
##     the tree-wreath product is generated by the images of generators
##     of <A>g,h</A> in <C>TreeWreathProduct(m,n,x0,y0)</C>.
##
##     <P/> For the operation on FR machines see <Ref
##     Oper="TreeWreathProduct" Label="FR machine"/>). It is described
##     (with small variations, and in lesser generality) in
##     <Cite Key="MR2197828"/>. For example, in
## <Example><![CDATA[
## gap> w := TreeWreathProduct(AddingGroup(2),AddingGroup(2),1,1);
## <recursive group over [ 1 .. 4 ] with 2 generators>
## gap> a := w.1; b := w.2;
## <Mealy element on alphabet [ 1 .. 4 ] with 3 states>
## <Mealy element on alphabet [ 1 .. 4 ] with 2 states>
## gap> Order(a); Order(b);
## infinity
## infinity
## gap> ForAll([-100..100],i->IsOne(Comm(a,a^(b^i))));
## true
## ]]></Example>
##     the group <C>w</C> is the wreath product <M>Z\wr Z</M>.
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Oper Name="WeaklyBranchedEmbedding" Arg="g"/>
##   <Returns>A embedding of <A>g</A> in a weakly branched group.</Returns>
##   <Description>
##     This function constructs a new FR group, on alphabet the square of the
##     alphabet of <A>g</A>. It is generated by the canonical copy of
##     <A>g</A> and by the tree-wreath product of <A>g</A> with an adding
##     machine on the same alphabet as <A>g</A> (see <Ref
##     Oper="TreeWreathProduct" Label="FR group"/>). The function returns a
##     group homomorphism into this new FR group.
##
##     <P/> The main result of <Cite Key="MR1995624"/> is that the
##     resulting group <M>h</M> is weakly branched. More precisely,
##     <M>h'</M> contains <M>|X|^2</M> copies of itself.
## <Code><![CDATA[
## gap> f := WeaklyBranchedEmbedding(BabyAleshinGroup);;
## gap> Range(f);
## <recursive group over [ 1 .. 4 ] with 8 generators>
## ]]></Code>
##     constructs a finitely generated branched group containing a free
##     subgroup.
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("TreeWreathProduct", [IsFRSemigroup, IsFRSemigroup, IsObject, IsObject]);
DeclareOperation("WeaklyBranchedEmbedding", [IsFRSemigroup]);
#############################################################################

#############################################################################
##
#O IsBranchingSubgroup
#O BranchingSubgroup
#O IsBranch
#O FindBranchingSubgroup
##
## <#GAPDoc Label="IsBranched">
## <ManSection>
##   <Oper Name="BranchingSubgroup" Arg="g"/>
##   <Returns>A branching subgroup of <A>g</A>.</Returns>
##   <Description>
##     This function searches for a subgroup <M>k</M> of <A>g</A>, such that
##     <M>k</M> contains <M>k \times \cdots \times k</M>.
##
##     <P/> It searches for elements in larger and larger balls in <A>g</A>,
##     calling <Ref Oper="FindBranchingSubgroup"/>.
## <Example><![CDATA[
## gap> K := BranchingSubgroup(GrigorchukGroup);
## <self-similar group over [ 1 .. 2 ] with 9 generators>
## gap> IsBranchingSubgroup(K);
## true
## gap> IsBranched(GrigorchukGroup);
## true
## gap> Index(GrigorchukGroup,K);
## 16
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Oper Name="FindBranchingSubgroup" Arg="g,l,r"/>
##   <Returns>A branching subgroup of <A>g</A>.</Returns>
##   <Description>
##     This function searches for a subgroup <M>k</M> of <A>g</A>, such that
##     <M>k</M> contains <M>k \times \cdots \times k</M>.
##
##     <P/> The second argument <A>l</A> specifies the level at which
##     branching must occur; i.e. asks to search for a subgroup <M>k</M>
##     such that <A>g</A> contains <M>k^{d^l}</M> where <M>d</M> is the
##     size of the alphabet. If <C>l=infinity</C>, the resulting <M>k</M>
##     will be a regularly branched subgroup.
##
##     <P/> The third argument <A>r</A> specifies the radius to explore in
##     <A>g</A> and all branching subgroups at levels smaller than <A>l</A>
##     for elements with all level-1 states trivial except one.
## <Example><![CDATA[
## gap> FindBranchingSubgroup(GrigorchukGroup,1,4);
## <self-similar group over [ 1 .. 2 ] with 8 generators>
## gap> Index(GrigorchukGroup,last);
## 8
## gap> FindBranchingSubgroup(GrigorchukGroup,2,4);
## <self-similar group over [ 1 .. 2 ] with 6 generators>
## gap> Index(GrigorchukGroup,last);
## 16
## gap> FindBranchingSubgroup(GrigorchukGroup,3,4);
## <self-similar group over [ 1 .. 2 ] with 9 generators>
## gap> Index(GrigorchukGroup,last);
## 16
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="IsBranched" Arg="g" Label="FR group"/>
##   <Returns><K>true</K> if <A>g</A> has a finite-index branching subgroup.</Returns>
##   <Description>
##     This function returns <K>true</K> if <A>g</A> has a finite-index
##     subgroup <M>k</M>, such that <M>k</M> contains
##     <M>k \times \cdots \times k</M>.
## <Example><![CDATA[
## <Example><![CDATA[
## gap> K := BranchingSubgroup(GrigorchukGroup);
## <self-similar group over [ 1 .. 2 ] with 9 generators>
## gap> IsBranchingSubgroup(K);
## true
## gap> IsBranched(GrigorchukGroup);
## true
## gap> Index(GrigorchukGroup,K);
## 16
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="IsBranchingSubgroup" Arg="k" Label="FR semigroup"/>
##   <Returns><K>true</K> if <A>k</A> is a branching subgroup.</Returns>
##   <Description>
##     This function returns <K>true</K> if <A>k</A> contains
##     <M>k \times \cdots \times k</M>.
## <Example><![CDATA[
## gap> K := BranchingSubgroup(GrigorchukGroup);
## <self-similar group over [ 1 .. 2 ] with 9 generators>
## gap> IsBranchingSubgroup(K);
## true
## gap> IsBranched(GrigorchukGroup);
## true
## gap> Index(GrigorchukGroup,K);
## 16
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="BranchStructure" Arg="G"/>
##   <Returns>A record describing the branching of <A>G</A>.</Returns>
##   <Description>
##     This function constructs a record with fields
##    <C>group,quo,set,top,wreath,epi</C> giving respectively
##    a group isomorphic to <C>G/K</C>,
##    the quotient map from <C>G</C> to it,
##    the alphabet of <C>G</C>,
##    the group of permutations of the alphabet,
##    the wreath product of <C>group</C> with its top permutations,
##    and an epimorphism from a subgroup of <C>wreath</C> to <C>group</C>.
##
##    <P/> This information is used as essential data on the branch group,
##    and are used to construct e.g. its Zeta function.
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute("BranchingSubgroup", IsFRGroup);
DeclareProperty("IsBranchingSubgroup", IsFRGroup);
DeclareProperty("IsBranched", IsFRGroup);
DeclareProperty("IsWeaklyBranched", IsFRGroup);

DeclareOperation("FindBranchingSubgroup", [IsFRGroup, IsObject, IsPosInt]);
DeclareAttribute("BranchStructure", IsFRGroup, "mutable");
#############################################################################

#############################################################################
## finite and recursive presentations
##
## <#GAPDoc Label="EpimorphismFromFpGroup">
## <ManSection>
##   <Oper Name="EpimorphismFromFpGroup" Arg="g,l"/>
##   <Returns>An epimorphism from a finitely presented group to <A>g</A>.</Returns>
##   <Description>
##     For some examples of self-similar groups, a recursive presentation of
##     the group is coded into <Package>FR</Package>, and an approximate
##     presentation is returned by this command,
##     together with a map onto the group <A>g</A>.
##     The argument <A>l</A> roughly means the number of iterates of an
##     endomorphism were applied to a finite set of relators. An isomorphic
##     group would be obtained by setting <C>l=infinity</C>; for that purpose,
##     see <Ref Oper="IsomorphismSubgroupFpGroup"/>.
##
##     <P/> Preimages can be computed, with <C>PreImagesRepresentativeNC</C>.
##     They are usually reasonably short words, though by no means guaranteed
##     to be of minimal length.
##
##     <P/> Currently this command is implemented through an ad hoc method
##     for <Ref Func="BinaryKneadingGroup"/>, <Ref Var="GrigorchukGroup"/>
##     and <Ref Var="GrigorchukOverGroup"/>.
## <Example><![CDATA[
## gap> f := EpimorphismFromFpGroup(GrigorchukGroup,1);
## MappingByFunction( <fp group on the generators
## [ a, b, c, d ]>, GrigorchukGroup, function( w ) ... end )
## 4 gap> RelatorsOfFpGroup(Source(f));
## [ a^2, b^2, c^2, d^2, b*c*d, a*d*a*d*a*d*a*d, a^-1*c*a*c*a^-1*c*a*c*a^-1*c*a*c*a^
##     -1*c*a*c, a^-1*c^-1*a*b*a^-1*c*a*b*a^-1*c^-1*a*b*a^-1*c*a*b*a^-1*c^-1*a*b*a^-1*
##     c*a*b*a^-1*c^-1*a*b*a^-1*c*a*b, a*d*a*c*a*c*a*d*a*c*a*c*a*d*a*c*a*c*a*d*a*c*a*c,
##   a^-1*c*a*c*a^-1*c*a*b*a^-1*c*a*b*a^-1*c*a*c*a^-1*c*a*b*a^-1*c*a*b*a^-1*c*a*c*a^
##     -1*c*a*b*a^-1*c*a*b*a^-1*c*a*c*a^-1*c*a*b*a^-1*c*a*b ]
## gap> PreImagesRepresentativeNC(f,Comm(GrigorchukGroup.1,GrigorchukGroup.2));
## a*c*a*d*a*d*a*c
## gap> Source(f).4^f=GrigorchukGroup.4;
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Oper Name="IsomorphismSubgroupFpGroup" Arg="g"/>
##   <Oper Name="AsSubgroupFpGroup" Arg="g"/>
##   <Oper Name="IsomorphismLpGroup" Arg="g"/>
##   <Oper Name="AsLpGroup" Arg="g"/>
##   <Returns>An isomorphism to a subgroup of a finitely presented group, or an L-presented group.</Returns>
##   <Description>
##     For some examples of self-similar groups, a recursive presentation of
##     the group is coded into <Package>FR</Package>, and is returned by this
##     command. The group <A>g</A> itself sits as a subgroup of a finitely
##     presented group. To obtain a finitely presented group approximating
##     <A>g</A>, see <Ref Oper="EpimorphismFromFpGroup"/>.
##
##     PreImages can also be computed; it is usually better to use
##     <C>PreImageElm</C>, since the word problem may not be solvable by
##     &GAP; in the f.p. group.
##
##     <P/> Currently this command is implemented through an ad hoc method
##     for <Ref Func="BinaryKneadingGroup"/>, <Ref Var="GrigorchukGroup"/>,
##     <Ref Var="GrigorchukOverGroup"/>, generalized
##     <Ref Func="GuptaSidkiGroups"/> and generalized
##     <Ref Func="FabrykowskiGuptaGroups"/>.
##
##     <P/> The second form returns an isomorphism to an L-presented group
##     (see <Cite Key="MR2009317"/> and <Cite Key="MR2483125"/>.
##     It requires the package <Package>NQL</Package>.
## <Example><![CDATA[
## gap> f := IsomorphismSubgroupFpGroup(BasilicaGroup);
## MappingByFunction( BasilicaGroup, Group([ a^-1, a*t^-1*a^-1*t*a^-1
##  ]), function( g ) ... end, function( w ) ... end )
## gap> Range(f);
## Group([ a^-1, a*t^-1*a^-1*t*a^-1 ])
## gap> c := Comm(BasilicaGroup.1,BasilicaGroup.2);
## <Mealy element on alphabet [ 1, 2 ] with 9 states, initial state 1>
## gap> c^f;
## t^-2*a*t^-1*a*t*a^-2*t*a*t^-2*a*t^-1*a*t*a^-1*t*a*t^-1*a*t^-2*
## a^-1*t*a*t^-1*a*t^-1*a^-1*t*a^-1*t^5*a*t^-1*a^-1*t*a^-1
## gap> PreImageElm(f,last);
## <Mealy element on alphabet [ 1, 2 ] with 9 states, initial state 1>
## gap> last=c;
## true
## ]]></Example>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareOperation("EpimorphismFromFpGroup", [IsFRGroup, IsInt]);
DeclareAttribute("IsomorphismSubgroupFpGroup", IsFRGroup);
DeclareAttribute("AsSubgroupFpGroup", IsFRGroup);
if not IsBound(IsomorphismLpGroup) then
    DeclareAttribute("IsomorphismLpGroup", IsFRGroup);
    DeclareOperation("AsLpGroup", [IsFRGroup]);
fi;
DeclareAttribute("FRGroupPreImageData",IsFRGroup);
DeclareAttribute("FRGroupImageData",IsFRGroup);
#############################################################################

#############################################################################
## VH structures
##
## <#GAPDoc Label="VHGroup">
## <ManSection>
##   <Oper Name="VHStructure" Arg="g"/>
##   <Filt Name="IsVHGroup" Arg="g"/>
##   <Returns>A VH-structure for the group <A>g</A>.</Returns>
##   <Description>
##     A <E>VH-structure</E> on a group <A>g</A> is a partition of the
##     generators in two sets <M>V,H</M> such that every relator of
##     <A>g</A> is of the form <M>vhv'h'</M>, and such that for all
##     <M>v\in V,h\in H</M> there exist unique <M>v'\in V,h'\in H</M>
##     such that <M>vhv'h'=1</M>.
##
##     <P/> The VH structure is stored as a record with fields <C>v,h</C>
##     containing lists of generators, and integer matrices
##     <C>transitions,output</C> such that <C>transitions[v][h']=v'</C> and
##     <C>output[v][h']=h</C>.
##
##     <P/> The filter recognizes groups with a VH structure.
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="VerticalAction" Arg="g"/>
##   <Attr Name="HorizontalAction" Arg="g"/>
##   <Returns>A homomorphism to an FR group.</Returns>
##   <Description>
##     A group with VH structure admits a <E>vertical action</E> of
##     its subgroup <M>\langle V\rangle</M>; this is the group generated
##     by the automaton <C>MealyMachine(trans,out)</C>. The function
##     returns the group homomorphism from the subgroup
##     <M>\langle V\rangle</M> to that FR group.
##
##     <P/> The horizontal action is that of the dual automaton (see
##     <Ref Oper="DualMachine"/>).
## <Example><![CDATA[
## gap> v := VerticalAction(RattaggiGroup.2_21);
## [ a1, a2, a3 ] -> [ <Mealy element on alphabet [ 1 .. 8 ] with 6 states>,
##                     <Mealy element on alphabet [ 1 .. 8 ] with 6 states>,
##                     <Mealy element on alphabet [ 1 .. 8 ] with 6 states> ]
## gap> RattaggiGroup.2_21.1^v;
## <Mealy element on alphabet [ 1 .. 8 ] with 6 states>
## gap> Range(v);
## <state-closed group over [ 1, 2, 3, 4, 5, 6, 7, 8 ] with 3 generators>
## gap> PermGroup(last,1);
## Group([ (3,4)(5,6), (1,7,8,2)(3,4,6,5), (1,7,5,3)(2,8,6,4) ])
## gap> DisplayCompositionSeries(last);
## G (3 gens, size 1344)
##  | A(1,7) = L(2,7) ~ B(1,7) = O(3,7) ~ C(1,7) = S(2,7) ~ 2A(1,7) = U(2,7) ~ A(2,2) = L(3,2)
## S (3 gens, size 8)
##  | Z(2)
## S (2 gens, size 4)
##  | Z(2)
## S (1 gens, size 2)
##  | Z(2)
## 1 (0 gens, size 1)
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Func Name="VHGroup" Arg="l1, l2, ..."/>
##   <Returns>A new VH group.</Returns>
##   <Description>
##     This function constructs the VH group specified by the squares
##     <A>l1, l2, ...</A>. Each <A>li</A> is a list of length 4, of the
##     form <C>[v,h,v',h']</C>. Here the entries are indices of
##     vertical, respectively horizontal generators, if positive; and their
##     inverses if negative.
## <Example><![CDATA[
## gap> # the Baby-Aleshin group
## gap> g := VHGroup([[1,1,-2,-1],[1,2,-3,-2],[2,1,-3,-1],
##                    [2,2,-2,-2],[3,1,-1,-2],[3,2,-1,-1]]);
## <VH group on the generators [ a1, a2, a3 | b1, b2 ]>
## gap> Display(g);
## generators = [ a1, a2, a3, b1, b2 ]                                          ## relators = [
##  a1*b1*a2^-1*b1^-1,
##  a1*b2*a3^-1*b2^-1,
##  a2*b1*a3^-1*b1^-1,
##  a2*b2*a2^-1*b2^-1,
##  a3*b1*a1^-1*b2^-1,
##  a3*b2*a1^-1*b1^-1 ]
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Prop Name="IsIrreducibleVHGroup" Arg="g"/>
##   <Returns>Whether <A>g</A> is an irreducible lattice.</Returns>
##   <Description>
##     A VH group is <E>irreducible</E> if its projections on both
##     trees is dense.
## <Example><![CDATA[
## gap> Display(RattaggiGroup.2_21);
## generators = [ a1, a2, a3, b1, b2, b3, b4 ]
## relators = [
##  a1*b1*a1^-1*b1^-1,
##  a1*b2*a1^-1*b2^-1,
##  a1*b3*a1^-1*b4^-1,
##  a1*b4*a2^-1*b3^-1,
##  a1*b4^-1*a2^-1*b3,
##  a2*b1*a2^-1*b2^-1,
##  a2*b2*a3^-1*b1,
##  a2*b3*a2^-1*b4,
##  a2*b2^-1*a3*b1^-1,
##  a3*b1*a3*b3^-1,
##  a3*b2*a3*b4^-1,
##  a3*b3*a3*b4 ]
## gap> IsIrreducibleVHGroup(RattaggiGroup.2_21);
## true
## ]]></Example>
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Attr Name="MaximalSimpleSubgroup" Arg="g"/>
##   <Returns>A maximal simple subgroup of <A>g</A>, if possible.</Returns>
##   <Description>
##     A VH group is never simple, but in favourable cases it admits a
##     finite-index simple subgroup, see <Cite Key="MR1446574"/>. This
##     function attempts to construct such a subgroup. It returns <K>fail</K>
##     if no such subgroup can be found.
##
##     <P/> The current implementation is not smart enough to work with the
##     Rattaggi examples (see <Ref Prop="IsVirtuallySimpleGroup"/>).
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute("VHStructure",IsFpGroup);
DeclareSynonym("IsVHGroup",IsFpGroup and HasVHStructure);
DeclareAttribute("VerticalAction",IsVHGroup);
DeclareAttribute("HorizontalAction",IsVHGroup);
DeclareAttribute("VHRws",IsVHGroup);
DeclareGlobalFunction("VHGroup");
DeclareProperty("IsIrreducibleVHGroup",IsGroup);
DeclareAttribute("LambdaElementVHGroup",IsVHGroup,"mutable");
DeclareAttribute("MaximalSimpleSubgroup",IsGroup);
#############################################################################

#############################################################################
##
#E GammaPQMachine
#E GammaPQGroup
##
## <#GAPDoc Label="GammaPQ">
## <ManSection>
##   <Func Name="GammaPQMachine" Arg="p, q"/>
##   <Func Name="GammaPQGroup" Arg="p, q"/>
##   <Returns>The quaternion-based machine / SC group.</Returns>
##   <Description>
##     The first function constructs a bireversible (see <Ref
##     Prop="IsBireversible"/>) Mealy machine based on quaternions,
##     see <Cite Key="MR1839488"/> and <Cite Key="MR1839489"/>.
##     This machine has <M>p+1</M> states indexed by
##     integer quaternions of norm <A>p</A>, and an alphabet of size
##     <M>q+1</M> indexed by quaternions of norm <A>q</A>. These quaternions
##     are congruent to <M>1\pmod 2</M> or <M>i\pmod 2</M> depending on
##     whether the odd prime <M>p</M> or <M>q</M> is <M>1</M> or
##     <M>3\pmod 4</M>.
##
##     <P/> The structure of the machine is such that there is a transition
##     from <M>(q,a)</M> to <M>(q',a')</M> precisely when <M>qa'=\pm q'a</M>.
##     In particular, the relations of the <Ref Oper="StructuralGroup"/>
##     hold up to a sign, when the alphabet/state letters are substituted
##     for the appropriate quaternions.
##
##     <P/> The quaternions themselves can be recovered through
##     <Ref Attr="Correspondence" Label="FR machine"/>, which is a list with
##     in first position the quaternions of norm <M>p</M> and in second
##     those of norm <M>q</M>.
##
##     <P/> The second function constructs the quaternion lattice that is the
##     <Ref Oper="StructuralGroup"/> of that machine. It has actions on two
##     trees, given by <Ref Oper="VerticalAction"/> and
##     <Ref Oper="HorizontalAction"/>; the ranges of these actions are groups
##     generated by automata, which are infinitely-transitive
##     (see <Ref Prop="IsInfinitelyTransitive"/>) and free by
##     <Cite Key="MR2155175" Where="Proposition 3.3"/>; see also
##     <Cite Key="MR713968"/>.
##   </Description>
## </ManSection>
##
## <ManSection>
##   <Var Name="RattaggiGroup"/>
##   <Description>
##     This record contains interesting examples of VH groups, that were studied by
##     Rattaggi in his PhD thesis <Cite Key="Rattaggi"/>. His Example 2.x appears
##     as <C>RattaggiGroup.2_x</C>.
##
##     <P/> The following summary of the examples' properties are copied from
##     Rattaggi's thesis. RF means "residually finite"; JI means "just infinite";
##     VS means "virtually simple".
##     <Table Align="r|c|c|c|c|c|c|c">
##       <Row>
##        <Item>Example</Item><Item><M>P_h</M></Item><Item><M>P_v</M></Item>
##        <Item>Irred?</Item><Item>Linear?</Item><Item>RF?</Item>
##        <Item>JI?</Item><Item>VS?</Item>
##       </Row>
##      <HorLine/>
##       <Row>
##        <Item>2.2</Item><Item>2tr</Item><Item>2tr</Item>
##        <Item>Y</Item><Item>N</Item><Item>N?</Item><Item>Y</Item><Item>Y?</Item>
##       </Row>
##       <Row>
##        <Item>2.15</Item>
##       </Row>
##       <Row>
##        <Item>2.18</Item>
##       </Row>
##       <Row>
##        <Item>2.21</Item>
##       </Row>
##       <Row>
##        <Item>2.26</Item><Item>2tr</Item><Item>q-prim</Item>
##        <Item>Y</Item><Item>N</Item><Item>N</Item><Item>N</Item><Item>N</Item>
##       </Row>
##       <Row>
##        <Item>2.30</Item><Item>2tr</Item><Item>2tr</Item>
##        <Item>Y</Item><Item>N</Item><Item>N</Item><Item>Y</Item><Item>Y?</Item>
##       </Row>
##       <Row>
##        <Item>2.36</Item>
##       </Row>
##       <Row>
##        <Item>2.39</Item>
##       </Row>
##       <Row>
##        <Item>2.43</Item><Item>2tr</Item><Item>2tr</Item>
##        <Item>Y</Item><Item>N</Item><Item>N</Item><Item>Y</Item><Item>Y</Item>
##       </Row>
##       <Row>
##        <Item>2.46</Item>
##       </Row>
##       <Row>
##        <Item>2.48</Item>
##       </Row>
##       <Row>
##        <Item>2.50</Item>
##       </Row>
##       <Row>
##        <Item>2.52</Item><Item>tr</Item><Item>2tr</Item>
##        <Item>Y</Item><Item>N</Item><Item>N</Item><Item>N</Item><Item>N</Item>
##       </Row>
##       <Row>
##        <Item>2.56</Item>
##       </Row>
##       <Row>
##        <Item>2.58</Item><Item>2tr</Item><Item>prim</Item>
##        <Item>Y</Item><Item>N</Item><Item>N?</Item><Item>N</Item><Item>N</Item>
##       </Row>
##       <Row>
##        <Item>2.70</Item>
##       </Row>
##      <HorLine/>
##       <Row>
##        <Item>3.26</Item><Item>2tr</Item><Item>2tr</Item>
##        <Item>Y</Item><Item>Y</Item><Item>Y</Item><Item>Y</Item><Item>N</Item>
##       </Row>
##       <Row>
##        <Item>3.28</Item>
##       </Row>
##       <Row>
##        <Item>3.31</Item>
##       </Row>
##       <Row>
##        <Item>3.33</Item>
##       </Row>
##       <Row>
##        <Item>3.36</Item>
##       </Row>
##       <Row>
##        <Item>3.38</Item>
##       </Row>
##       <Row>
##        <Item>3.40</Item>
##       </Row>
##       <Row>
##        <Item>3.44</Item>
##       </Row>
##       <Row>
##        <Item>3.46</Item>
##       </Row>
##       <Row>
##        <Item>3.72</Item>
##       </Row>
##     </Table>
##   </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareGlobalFunction("GammaPQMachine");
DeclareGlobalFunction("GammaPQGroup");
#############################################################################