In this chapter we present the functionality applicable to elements of groups and semigroups.
TreeAutomorphism(
states,
perm ) O
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)
TreeHomomorphism(
states,
tr ) O
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]
Representative(
word,
fam ) O
Representative(
word,
a ) O
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)
IsSphericallyTransitive(
a ) [treehom] P
Returns whether the action of a is spherically transitive (see Short math background).
IsTransitiveOnLevel(
a,
lev ) [treehom] O
Returns whether a acts transitively on level lev of the tree.
IsOne(
a ) O
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
IsOneContr(
a ) F
Returns true
if a is trivial automorphism and false
otherwise. Works for
contracting groups only. Uses polynomial time algorithm.
Order(
a ) O
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
OrderUsingSections(
a[,
max_depth] ) O
Tries to compute the order of the element a by looking at its sections
of depth up to max_depthth 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
Perm(
a[,
lev] ) O
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).
PermOnLevel(
a,
k ) O
Does the same thing as Perm
(Perm).
PermOnLevelAsMatrix(
g,
lev ) F
Computes the action of the element g of a group on the levth level as a permutational matrix, in which the ith 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 ] ]
TransformationOnLevel(
a,
lev ) O
TransformationOnFirstLevel(
a ) O
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
).
TransformationOnLevelAsMatrix(
g,
lev ) F
Computes the action of the element g on the levth level as a permutational matrix, in which the ith 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 ] ]
Word(
a ) O
Returns a as an associative word (an element of the underlying free group) in the generators of the selfsimilar 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
The multiplication of tree homomorphisms is defined in the standard way
a *
b
The following operations allow computation of the actions of tree homomorphisms on letters and vertices
letter ^
a
vertex ^
a
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.
Section(
a,
v ) [treehom] O
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
Sections(
a [,
lev] ) O
Returns the list of sections of a at the levth 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 ]
Decompose(
a[,
k] ) O
Returns the decomposition of the tree homomorphism a on the kth level of the tree, i.e. the
representation of the form

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)
a in
G
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
OrbitOfVertex(
ver,
g[,
n] ) O
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 ] ]
PrintOrbitOfVertex(
ver,
g[,
n] ) O
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
PermActionOnLevel(
perm,
big_lev,
sm_lev,
deg ) F
Given a permutation perm on the big_levth 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)
IsFiniteState(
a ) [selfsim] P
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 finitestate property or if a is not finitestate (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
AllSections(
a ) A
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 selfsimilar (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.
AutomPortrait(
a ) F
AutomPortraitBoundary(
a ) F
AutomPortraitDepth(
a ) F
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_{1},g_{2},…,g_{d})σ the portrait of g is [σ, AutomPortrait(g_{1}),…, 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 ith 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]
automgrp manual