3 Properties and operations with group and semigroup elements

Constructs the tree automorphism with states on the first level given by the argument states and acting on the first level as the permutation perm. The states must belong to the same family.

gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> r := TreeAutomorphism([p, q, p, q^2],(1,2)(3,4));
(p, q, p, q^2)(1,2)(3,4)
gap> t := TreeAutomorphism([q, 1, p*q, q],(1,2));
(q, 1, p*q, q)(1,2)
gap> r*t;
(p, q^2, p*q, q^2*p*q)(3,4)

Constructs an homomorphism with states states and acting on the first level with transformation tr. The states must belong to the same family.

gap> S := AutomatonSemigroup("a=(a,b)[1,1],b=(b,a)(1,2)");
< a, b >
gap> x := TreeHomomorphism([a,b^2,a,a*b],Transformation([3,1,2,2]));
(a, b^2, a, a*b)[3,1,2,2]
gap> y := TreeHomomorphism([a*b,b,b,b^2],Transformation([1,4,2,3]));
(a*b, b, b, b^2)[1,4,2,3]
gap> x*y;
(a*b, b^2*a*b, a*b, a*b^2)[2,1,4,4]

Given an associative word word constructs the tree homomorphism from the family fam, or to which homomorphism a belongs. This function is useful when one needs to make some operations with associative words. See also Word (Word).

gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> F := UnderlyingFreeGroup(L);
<free group on the generators [ p, q ]>
gap> r := Representative(F.1*F.2^2, p);
p*q^2
gap> Decompose(r);
(p*q^2, q*p^2)(1,2)
gap> H := SelfSimilarGroup("x=(x*y,x)(1,2), y=(x^-1,y)");
< x, y >
gap> F := UnderlyingFreeGroup(H);
<free group on the generators [ x, y ]>
gap> r := Representative(F.1^-1*F.2, x);
x^-1*y
gap> Decompose(r);
(x^-1*y, y^-1*x^-2)(1,2)

3.2 Properties and attributes of tree automorphisms and homomorphisms

Returns whether the action of a is spherically transitive (see Short math background).

Returns whether a acts transitively on level lev of the tree.

Returns whether an automorphism a acts trivially on the tree. For contracting groups see also UseContraction (UseContraction) and IsOneContr (IsOneContr).

gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> IsOne(q*p^-1*q*p^-1);
true

Returns true if a is trivial automorphism and false otherwise. Works for contracting groups only. Uses polynomial time algorithm.

Computes the order of an automorphism a. In some cases it does not stop. Works always (modulo memory restrictions) for groups generated by bounded automata.

If InfoLevel of InfoAutomGrp is greater than or equal to 3 (one can set it by SetInfoLevel( InfoAutomGrp, 3)) and the element has infinite order, then the proof of this fact is printed.

gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> Order(p*q^-1);
2
gap> SetInfoLevel( InfoAutomGrp, 3);
gap> Order( u^35*v^-12*u^2*v^-3 );
#I  (u^35*v^-12*u^2*v^-3)^68719476736 has conjugate of u^2*v^-3*u^35*v^
-12 as a section at vertex [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ]
infinity

Tries to compute the order of the element a by looking at its sections of depth up to max_depth-th level. If max_depth is omitted it is assumed to be infinity, but then it may not stop. Also note, that if max_depth is not given, it searches the tree in depth first and may be trapped in some infinite ray, while specifying finite max_depth may produce a result by looking at a section not in that ray. For bounded automata it will always produce a result.

If InfoLevel of InfoAutomGrp is greater than or equal to 3 (one can set it by SetInfoLevel( InfoAutomGrp, 3)) and the element has infinite order, then the proof of this fact is printed.

gap> Grigorchuk_Group := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> OrderUsingSections( a*b*a*c*b );
16
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
gap> SetInfoLevel( InfoAutomGrp, 3);
gap> OrderUsingSections( u^23*v^-2*u^3*v^15, 10 );
#I  v^13*u^15 acts transitively on levels and is obtained from (u^23*v^-2*u^3*v^15)^1
    by taking sections and cyclic reductions at vertex [ 1 ]
infinity
gap> G := AutomatonGroup("a=(c,a)(1,2), b=(b,c), c=(b,a)");
< a, b, c >
gap> OrderUsingSections(b,10);
#I  b*c*a^2*b^2*c*a acts transitively on levels and is obtained from (b)^8
    by taking sections and cyclic reductions at vertex
[ 2, 2, 1, 1, 1, 1, 2, 2, 1, 1 ]
infinity

Returns the permutation induced by the tree automorphism a on the level lev (or first level if lev is not given). See also TransformationOnLevel (TransformationOnLevel).

Does the same thing as Perm (Perm).

Computes the action of the element g of a group on the lev-th level as a permutational matrix, in which the i-th row contains 1 at the position i^g.

gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> PermOnLevel(p*q,2);
(1,4)(2,3)
gap> PermOnLevelAsMatrix(p*q, 2);
[ [ 0, 0, 0, 1 ], [ 0, 0, 1, 0 ], [ 0, 1, 0, 0 ], [ 1, 0, 0, 0 ] ]

The first function returns the transformation induced by the tree homomorphism a on the level lev. See also PermOnLevel (PermOnLevel).

If the transformation is invertible then it returns a permutation, and Transformation otherwise.

TransformationOnFirstLevel(a) is equivalent to TransformationOnLevel(a, 1).

Computes the action of the element g on the lev-th level as a permutational matrix, in which the i-th row contains 1 at the position i^g.

gap> L := AutomatonSemigroup("p=(p,q)(1,2), q=(p,q)[1,1]");
< p, q >
gap> TransformationOnLevel(p*q,2);
Transformation( [ 1, 1, 2, 2 ] )
gap> TransformationOnLevelAsMatrix(p*q,2);
[ [ 1, 0, 0, 0 ], [ 1, 0, 0, 0 ], [ 0, 1, 0, 0 ], [ 0, 1, 0, 0 ] ]

Returns a as an associative word (an element of the underlying free group) in the generators of the self-similar group (semigroup) to which a belongs.

gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> w := Word(p*q^2*p^-1);
p*q^2*p^-1
gap> Length(w);
4

3.3 Operations with tree automorphisms and homomorphisms

The multiplication of tree homomorphisms is defined in the standard way

The following operations allow computation of the actions of tree homomorphisms on letters and vertices

gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> 1^p;
2
gap> [1, 2, 2, 1, 2, 1]^(p*q^2);
[ 2, 1, 2, 2, 1, 2 ]

The operations below describe how to work with sections of tree homomorphisms.

Returns the section of the automorphism (homomorphism) a at the vertex v. The vertex v can be a list representing the vertex, or a positive integer representing a vertex of the first level of the tree.

gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> Section(p*q*p^2, [1,2,2,1,2,1]);
p^2*q^2

Returns the list of sections of a at the lev-th level. If lev is omitted it is assumed to be 1.

gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> Sections(p*q*p^2);
[ p*q^2*p, q*p^2*q ]

Returns the decomposition of the tree homomorphism a on the k-th level of the tree, i.e. the representation of the form

a = (a1, a2, …, ad1×·.·×dk)σ

where a_i are the sections of a at the k-th level, and σ is the transformation of the k-th level. If k is omitted it is assumed to be 1.

gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> Decompose(p*q^2);
(p*q^2, q*p^2)(1,2)
gap> Decompose(p*q^2,3);
(p*q^2, q*p^2, p^2*q, q^2*p, p*q*p, q*p*q, p^3, q^3)(1,8,3,5)(2,7,4,6)

Returns whether the automorphism a belongs to the group G. In some cases it does not stop.

gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> H := Group([p^2, q^2]);
< p^2, q^2 >
gap> p in H;
false

Returns the list of vertices in the orbit of the vertex ver under the action of the semigroup generated by the automorphism g. If n is specified, it returns only the first n elements of the orbit. Vertices are defined either as lists with entries from {1,…,d}, or as strings containing characters 1,…,d, where d is the degree of the tree.

gap> T := AutomatonGroup("t=(1,t)(1,2)");
< t >
gap> OrbitOfVertex([1,1,1], t);
[ [ 1, 1, 1 ], [ 2, 1, 1 ], [ 1, 2, 1 ], [ 2, 2, 1 ], [ 1, 1, 2 ],
  [ 2, 1, 2 ], [ 1, 2, 2 ], [ 2, 2, 2 ] ]
gap> OrbitOfVertex("11111111111", t, 6);
[ [ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ], [ 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
  [ 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1 ], [ 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1 ],
  [ 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1 ], [ 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1 ] ]

Prints the orbit of the vertex ver under the action of the semigroup generated by g. Each vertex is printed as a string containing characters 1,…,d, where d is the degree of the tree. In case of binary tree the symbols `` '' and ``x'' are used to represent 1 and 2. If n is specified only the first n elements of the orbit are printed. Vertices are defined either as lists with entries from {1,…,d}, or as strings. See also OrbitOfVertex (OrbitOfVertex).

gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> PrintOrbitOfVertex("2222222222222222222222222222222", p*q^-2, 6);
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
 x x x x x x x x x x x x x x x
x  xx  xx  xx  xx  xx  xx  xx
   x   x   x   x   x   x   x
xxx    xxxx    xxxx    xxxx
 x     x x     x x     x x
gap> H := AutomatonGroup("t=(s,1,1)(1,2,3), s=(t,s,t)(1,2)");
< t, s >
gap> PrintOrbitOfVertex([1,2,1], s^2);
121
132
123
131
122
133

Given a permutation perm on the big_lev-th level of the tree of degree deg returns the permutation induced by perm on a smaller level sm_lev.

gap> PermActionOnLevel((1,4,2,3), 2, 1, 2);
(1,2)
gap> PermActionOnLevel((1,13,5,9,3,15,7,11)(2,14,6,10,4,16,8,12), 4, 2, 2);
(1,4,2,3)

3.4 Elements of groups and semigroups defined by wreath recursion

Returns true if a has finitely many different sections. It will never stop if the free reduction of words is not sufficient to establish the finite-state property or if a is not finite-state (has infinitely many different sections).

See also AllSections (AllSections) for the list of all sections and MealyAutomaton (MealyAutomaton), which allows to construct a Mealy automaton whose states are the sections of a and which encodes its action on the tree.

gap> D := SelfSimilarGroup("x=(1,y)(1,2), y=(z^-1,1)(1,2), z=(1,x*y)");
< x, y, z >
gap> IsFiniteState(x*y^-1);
true

Returns the list of all sections of a if there are finitely many of them and this fact can be established using free reduction of words in sections. Otherwise will never stop. Note, that in the case when a is an element of a self-similar (semi)group defined by wreath recurion it does not check whether all elements of the list are actually different automorphisms (homomorphisms) of the tree. If a is a element of of a (semi)group generated by finite automaton, it will always return the list of all distinct sections of a.

gap> D := SelfSimilarGroup("x=(1,y)(1,2), y=(z^-1,1)(1,2), z=(1,x*y)");
< x, y, z >
gap> AllSections(x*y^-1);
[ x*y^-1, z, 1, x*y, y*z^-1, z^-1*y^-1*x^-1, y^-1*x^-1*z*y^-1, z*y^-1*x*y*z,
  y*z^-1*x*y, z^-1*y^-1*x^-1*y*z^-1, x*y*z, y, z^-1, y^-1*x^-1, z*y^-1 ]

See also operation MealyAutomaton (MealyAutomaton), which allows to construct a Mealy automaton whose states are the sections of given tree homomorphism and which encodes its action on the tree.

3.5 Elements of contracting groups

Constructs the portrait of an element a of a contracting group G. The portrait of a is defined recursively as follows. For g in the nucleus of G the portrait is just [g]. For any other element g=(g₁,g₂,…,g_d)σ the portrait of g is [σ, AutomPortrait(g₁),…, AutomPortrait(g_d)], where d is the degree of the tree. This structure describes a finite tree whose inner vertices are labelled by permutations from S_d and the leaves are labelled by elements from the nucleus. The contraction in G guarantees that the portrait of any element is finite.

The portraits may be considered as ``normal forms'' of the elements of G, since different elements have different portraits.

One also can be interested only in the boundary of a portrait, which consists of all leaves of the portrait. This boundary can be described by an ordered set of pairs [level_i, g_i], i=1,…,r representing the leaves of the tree ordered from left to right (where level_i and g_i are the level and the label of the i-th leaf correspondingly, r is the number of leaves). The operation AutomPortraitBoundary(a) computes this boundary.

AutomPortraitDepth( a ) returns the depth of the portrait, i.e. the minimal level such that all sections of a at this level belong to the nucleus of G.

gap> Basilica := AutomatonGroup("u=(v,1)(1,2), v=(u,1)");
< u, v >
gap> AutomPortrait(u^3*v^-2*u);
[ (), [ (), [ (), [ v ], [ v ] ], [ 1 ] ],
  [ (), [ (), [ v ], [ u^-1*v ] ], [ v^-1 ] ] ]
gap> AutomPortrait(u^3*v^-2*u^3);
[ (), [ (), [ (1,2), [ (), [ (), [ v ], [ v ] ], [ 1 ] ], [ v ] ], [ 1 ] ],
  [ (), [ (1,2), [ (), [ (), [ v ], [ v ] ], [ 1 ] ], [ u^-1*v ] ], [ v^-1 ]
     ] ]
gap> AutomPortraitBoundary(u^3*v^-2*u^3);
[ [ 5, v ], [ 5, v ], [ 4, 1 ], [ 3, v ], [ 2, 1 ], [ 5, v ], [ 5, v ],
  [ 4, 1 ], [ 3, u^-1*v ], [ 2, v^-1 ] ]
gap> AutomPortraitDepth(u^3*v^-2*u^3);
5

[Up] [Previous] [Next] [Index]