% This file was created automatically from elements.msk. % DO NOT EDIT! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Chapter{Properties and operations with group and semigroup elements}
In this chapter we present the functionality applicable to elements of groups and semigroups.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Creation of tree automorphisms and homomorphisms}
\>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. \beginexample
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) \endexample
\>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. \beginexample
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] \endexample
\>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"). \beginexample
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) \endexample
%Declaration{AutomFamily}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Properties and attributes of tree automorphisms and homomorphisms}
\>IsSphericallyTransitive( <a> )!{ for tree homomorphism} P
Returns whether the action of <a> is spherically transitive (see "Short math background").
\>IsTransitiveOnLevel( <a>, <lev> )!{ for tree homomorphism} 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"). \beginexample
gap> L := AutomatonGroup("p=(p,q)(1,2), q=(p,q)");
< p, q >
gap> IsOne(q*p^-1*q*p^-1);
true \endexample
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.
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.
\beginexample
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 \endexample
\>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 <lev>-th level as a permutational matrix, in
which the i-th row contains 1 at the position i^<g>. \beginexample
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 ] ] \endexample
\>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.
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>. \beginexample
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 ] ] \endexample
\>Word( <a> ) O
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. \beginexample
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 \endexample
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Operations with tree automorphisms and homomorphisms}
The multiplication of tree homomorphisms is defined in the standard way
\>`<a> \* <b>'{product}!{ for tree homomorphisms}
The following operations allow computation of the actions of tree
homomorphisms on letters and vertices
\>`<letter> ^ <a>'{action}!{ of tree homomorphism on letter} \>`<vertex> ^ <a>'{action}!{ of tree homomorphism on vertex}
The operations below describe how to work with sections of tree homomorphisms.
\>Section( <a>, <v> )!{ for tree homomorphism} 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. \beginexample
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 \endexample
\>Sections( <a> [, <lev>] ) O
Returns the list of sections of <a> at the <lev>-th level. If <lev> is omitted
it is assumed to be 1. \beginexample
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 ] \endexample
\>Decompose( <a>[, <k>] ) O
Returns the decomposition of the tree homomorphism <a> on the <k>-th level of the tree, i.e. the
representation of the form $$a = (a_1, a_2, \ldots, a_{d_1\times...\times d_k})\sigma$$
where $a_i$ are the sections of <a> at the <k>-th level, and $\sigma$ is the
transformation of the <k>-th level. If <k> is omitted it is assumed to be 1. \beginexample
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) \endexample
\>`<a> in <G>'{in}
Returns whether the automorphism <a> belongs to the group <G>. In some cases it does not stop. \beginexample
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 \endexample
\>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,\ldots,d\}$, or as
strings containing characters $1,\ldots,d$, where $d$
is the degree of the tree. \beginexample
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 ] ] \endexample
\>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,\ldots,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,\ldots,d\}$, or as
strings. See also `OrbitOfVertex' ("OrbitOfVertex"). \beginexample
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 \endexample
\>PermActionOnLevel( <perm>, <big_lev>, <sm_lev>, <deg> ) F
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>. \beginexample
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) \endexample
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Elements of groups and semigroups defined by wreath recursion}
\>IsFiniteState( <a> )!{ for tree homomorphism} P
Returns `true' if 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. \beginexample
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 \endexample
\>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 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>. \beginexample
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 ] \endexample
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.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Elements of contracting groups}
\>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,\ldots,g_d)\sigma$ the portrait of $g$ is
$[\sigma, `AutomPortrait'(g_1),\ldots, `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,\ldots,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'()
computes this boundary.
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
