<html><head><title>[automgrp] 1 Introduction</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP002.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>1 Introduction</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP001.htm#SECT001">Short math background</a>
<li> <A HREF="CHAP001.htm#SECT002">Installation instructions</a>
<li> <A HREF="CHAP001.htm#SECT003">Quick example</a>
</ol><p>
<p>
The <code>AutomGrp</code> package provides methods for computations with groups and
semigroups generated by finite automata or given by wreath recursions, as well
as with their finitely generated subgroups, subsemigroups and elements.
<p>
The project originally started in 2000 mostly for personal use.
It was gradually expanding during consequent years, including both
addition of new algorithms and simplification of user interface. It
was used in the process of classification of groups generated by
3-state automata over a 2-letter alphabet (see
<a href="biblio.htm#BGK06"><cite>BGK06</cite></a>, <a href="biblio.htm#BGK07"><cite>BGK07</cite></a>).
<p>
First author thanks Sveta and Max Muntyan for their infinite patience and
understanding. Second author thanks Olga and Anna Savchuk for their help
and understanding. This project would be impossible without them.
<p>
We would like to express our warm gratitude to Rostislav Grigorchuk, Zoran Sunic,
Volodymyr Nekrashevych, Ievgen Bondarenko, Rostyslav Kravchenko, Yaroslav and Maria
Vorobets and Ben Steinberg for their support, valuable comments, feature requests and constant interest
in the project.
<p>
Both authors were partially supported by NSF grants DMS-0600975, DMS-0456185 and DMS-0308985.
<p>
<p>
<h2><a name="SECT001">1.1 Short math background</a></h2>
<p><p>
This package deals mostly with groups acting on rooted trees. In
this section we recall necessary definitions and notation that will
be used throughout the manual. For more detailed introduction in the
theory of groups generated by automata we refer the reader
to <a href="biblio.htm#GNS00"><cite>GNS00</cite></a>.
<p>
The infinite connected tree with selected vertex, called
the <var>root</var>, in which the degree of every vertex except the root is
<i>d</i>+1 and the degree of the root is <i>d</i> is called the <var>regular
homogeneous rooted tree of degree <i>d</i> (or <i>d</i>-ary
tree)</var>. The rooted tree of degree 2 is called the <var>binary tree</var>.
<p>
The <i>n</i>-th <var>level</var> of the tree consists of all vertices located at
distance <i>n</i> from the root (here we mean combinatorial distance in
the graph).
<p>
Similarly one defines <var>spherically homogeneous</var> (or <var>spherically-transitive</var>)
rooted trees as rooted trees, such that the degrees of all vertices on the same level
coincide.
<p>
Given a finite alphabet <i>X</i>={1,2,…,<i>d</i>} the set <i>X</i><sup>*</sup> of all
finite words over <i>X</i> may be endowed with the structure of <i>d</i>-ary
tree in which the empty word ∅ is the <var>root</var>, the <var>level</var>
<i>n</i> in <i>X</i><sup>*</sup> consists of the words of length <i>n</i> over <i>X</i> and
every vertex <i>v</i> has <i>d</i> children, labeled by <i>vx</i>, for <i>x</i> ∈ <i>X</i>.
<p>
Any automorphism <i>f</i> of the rooted tree <i>T</i> fixes the root and the
levels. For any vertex <i>v</i> of the tree the automorphism <i>f</i> induces the
automorphism <i>f</i>|<sub><i>v</i></sub> of the subtree hanging down from the vertex <i>v</i> by
<i>f</i>|<sub><i>v</i></sub>(<i>u</i>)=<i>w</i> if <i>f</i>(<i>vu</i>)=<i>v</i>′<i>w</i> for some <i>v</i>′ ∈ <i>X</i><sup>|<i>v</i>|</sup> from the same
level as <i>v</i> (here |<i>v</i>| denotes the combinatorial distance from <i>v</i> to
the root of the tree). This automorphism is called <var>the section</var> of <i>f</i> at
<i>v</i>.
<p>
If the tree <i>T</i> is regular, then the subtrees hanging down from
vertices of <i>T</i> are canonically isomorphic to <i>T</i> and, thus, the
sections of any automorphism <i>f</i> of <i>T</i> can be considered as
automorphisms of <i>T</i> again.
<p>
A group <i>G</i> of automorphisms of the regular rooted tree <i>T</i> is called
<var>self-similar</var> if all sections of every element of <i>G</i> belong to
<i>G</i>.
<p>
A self-similar group <i>G</i> is called <var>contracting</var>
if there is a finite set <i>N</i> of elements of <i>G</i>, such that for any
<i>g</i> in <i>G</i> there is a level <i>n</i> such that all sections of <i>g</i> at
vertices of levels bigger than <i>n</i> belong to <i>N</i>. The smallest set
with such a property is called the <var>nucleus</var> of <i>G</i>.
<p>
Any automorphism <i>f</i> of a rooted tree can be decomposed as
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>f</i>=(<i>f</i><sub>1</sub>,<i>f</i><sub>2</sub>,…,<i>f</i><sub><i>d</i></sub>)σ,</td></tr></table></td></tr></table>
<p>
where <i>f</i><sub>1</sub>,…,<i>f</i><sub><i>d</i></sub> are the sections of <i>f</i> at the vertices of
the first level and σ is the permutation which permutes the subtrees
hanging down from these vertices.
<p>
This notation is very convenient for performing multiplication of
elements. If <i>f</i>=(<i>f</i><sub>1</sub>,<i>f</i><sub>2</sub>,…,<i>f</i><sub><i>d</i></sub>)σ and
<i>g</i>=(<i>g</i><sub>1</sub>,<i>g</i><sub>2</sub>,…,<i>g</i><sub><i>d</i></sub>)π, then
<p>
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>f</i>·<i>g</i>=(<i>f</i><sub>1</sub>·<i>g</i><sub>σ(1)</sub>,…,<i>f</i><sub><i>d</i></sub>·<i>g</i><sub>σ(<i>d</i>)</sub>)σπ,</td></tr></table></td></tr></table>
<p>
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>f</i><sup>−1</sup>=(<i>f</i><sub>σ<sup>−1</sup>(1)</sub><sup>−1</sup>,…,<i>f</i><sub>σ<sup>−1</sup>(<i>d</i>)</sub><sup>−1</sup>)σ<sup>−1</sup>.</td></tr></table></td></tr></table>
<p>
The group of automorphisms of a rooted tree is said to be
<var>level-transitive</var> if it acts transitively on each level of the
tree.
<p>
Everything above applies also for homomorphisms of rooted trees
(maps preserving the root and incidence relation of the vertices).
The only difference is that in this case we get semigroups and
monoids of tree homomorphisms.
<p>
A special class of self-similar groups is the class of groups
generated by finite automata. This class is especially nice from
algorithmic point of view. Recall basic definitions.
<p>
A <var>Mealy automaton</var> (<var>transducer</var>, <var>synchronous automaton</var>, or,
simply, <var>automaton</var>) is a tuple <i>A</i>=(<i>Q</i>,<i>X</i>,ρ,τ), where <i>Q</i> is
a set of <var>states</var>, <i>X</i> is a finite <var>alphabet</var> of cardinality <i>d</i> ≥ 2, ρ:<i>Q</i> ×<i>X</i> → <i>X</i> is a map, called <var>output map</var>, τ:<i>Q</i> ×<i>X</i> → <i>Q</i> is a map, called <var>transition map</var>.
<p>
If for each state <i>q</i> in <i>Q</i>, the restriction ρ<sub><i>q</i></sub>: <i>X</i> → <i>X</i>
given by ρ<sub><i>q</i></sub>(<i>x</i>)=ρ(<i>q</i>,<i>x</i>) is a permutation, the automaton is
called <var>invertible</var>.
<p>
If the set <i>Q</i> of states is finite, the automaton is called
<var>finite</var>.
<p>
If some state <i>q</i> in <i>Q</i> of the automaton <i>A</i> is selected to be initial,
the automaton is called <var>initial</var> and denoted <i>A</i><sub><i>q</i></sub>. If an initial
state is not specified, the automaton is called <var>noninitial</var>.
<p>
An initial automaton naturally acts on <i>X</i><sup>*</sup> by homomorphisms
(automorphisms in case of an invertible automation). Given a word
<i>x</i><sub>1</sub><i>x</i><sub>2</sub>…<i>x</i><sub><i>n</i></sub> the automaton starts at the initial state <i>q</i>,
reads the first input letter <i>x</i><sub>1</sub>, outputs the letter ρ<sub><i>q</i></sub>(<i>x</i><sub>1</sub>)
and changes its state to <i>q</i><sub>1</sub>=τ(<i>q</i>,<i>x</i><sub>1</sub>). The rest of the input
word is handled by the new state <i>q</i><sub>1</sub> in the same way. Formally
speaking, the functions ρ and τ can be extended to ρ:<i>Q</i> ×<i>X</i><sup>*</sup> → <i>X</i><sup>*</sup> and τ:<i>Q</i> ×<i>X</i><sup>*</sup> → <i>Q</i>.
<p>
Given an automaton <i>A</i> the group <i>G</i>(<i>A</i>) of automorphisms of <i>X</i><sup>*</sup>
generated by the states of <i>A</i> (as initial automata) is called the
<var>automaton group</var> defined by <i>A</i>.
<p>
Every automaton group is self-similar, because the section of <i>A</i><sub><i>q</i></sub>
at vertex <i>v</i> is just <i>A</i><sub>τ(<i>q</i>,<i>v</i>)</sub>.
<p>
A special case is the case of groups generated by finite automata
and their subgroups. In this class we can solve the word problem,
which makes it much nicer from computational point of view.
<p>
Finite automata are often described by <var>recursive relations</var> of
the form
<p>
<br clear="all" /><table border="0" width="100%"><tr><td><table align="center" cellspacing="0" cellpadding="2"><tr><td nowrap="nowrap" align="center"><i>q</i>=(τ(<i>q</i>,1),…,τ(<i>q</i>,<i>d</i>)) ρ<sub><i>q</i></sub></td></tr></table></td></tr></table>
<p>
for every state <i>q</i>. For example, the line <i>a</i>=(<i>a</i>,<i>b</i>)(1,2), <i>b</i>=(<i>a</i>,<i>b</i>)
describes the automaton with 2 states <i>a</i> and <i>b</i>, such that <i>a</i>
permutes the letters 1 and 2 and <i>b</i> does not; and independently
of current state the automaton changes its initial state to <i>a</i> if
it reads 1 and to <i>b</i> if it reads 2. This particular automaton
generates the, so-called, Lamplighter group.
<p>
One may also consider semigroups generated by noninvertible
automata.
<p>
<p>
<h2><a name="SECT002">1.2 Installation instructions</a></h2>
<p><p>
<code>AutomGrp</code> package requires <font face="Gill Sans,Helvetica,Arial">GAP</font> version at least 4.4.6 and <code>FGA</code> (Free
Group Algorithms) package available at <a href="http://www.gap-system.org/Packages/fga.html">http://www.gap-system.org/Packages/fga.html</a>
<p>
The installation of the <code>AutomGrp</code> package follows the standard <font face="Gill Sans,Helvetica,Arial">GAP</font> rules, i.e.
to install it unpack the archive into the <code>pkg</code> directory of
your GAP distribution. This will create <code>automgrp</code> subdirectory.
<p>
To load package issue the command
<pre>
gap> LoadPackage("automgrp");
-----------------------------------------------------------------------------
Loading AutomGrp 1.1.1 (Automata Groups)
by Yevgen Muntyan (http://www.math.tamu.edu/~muntyan/) and
Dmytro Savchuk (http://www.math.tamu.edu/~savchuk/).
-----------------------------------------------------------------------------
true
</pre>
<p>
To test the installation, issue the command
<pre>
gap> Read( Filename( DirectoriesLibrary( "pkg/automgrp/tst"), "testall.g"));
</pre>
in the <font face="Gill Sans,Helvetica,Arial">GAP</font> command line.
<p>
<p>
<h2><a name="SECT003">1.3 Quick example</a></h2>
<p><p>
Here is how to define Grigorchuk group and Basilica group.
<p>
<pre>
gap> GrigorchukGroup := AutomatonGroup("a=(1,1)(1,2),b=(a,c),c=(a,d),d=(1,b)");
< a, b, c, d >
gap> Basilica := AutomatonGroup( "u=(v,1)(1,2), v=(u,1)" );
< u, v >
</pre>
<p>
Similarly one can define a group (or semigroup) generated by
a noninvertible automaton. As an example we consider the semigroup of
intermediate growth generated by the two state automaton
(<a href="biblio.htm#BRS06"><cite>BRS06</cite></a>)
<p>
<pre>
gap> SG := AutomatonSemigroup( "f0=(f0,f0)(1,2), f1=(f1,f0)[2,2]" );
< f0, f1 >
</pre>
<p>
Another type of groups (semigroups) implemented in the package is
the class of groups (semigroups) defined by wreath recursion
(finitely generated self-similar groups).
<p>
<pre>
gap> WRG := SelfSimilarGroup("x=(1,y)(1,2),y=(z^-1,1)(1,2),z=(1,x*y)");
< x, y, z >
</pre>
<p>
Now we can compute several properties of <code>GrigorchukGroup</code>, <code>Basilica</code> and <code>SG</code>
<p>
<pre>
gap> IsFinite(GrigorchukGroup);
false
gap> IsSphericallyTransitive(GrigorchukGroup);
true
gap> IsFractal(GrigorchukGroup);
true
gap> IsAbelian(GrigorchukGroup);
false
gap> IsTransitiveOnLevel(GrigorchukGroup, 4);
true
</pre>
<p>
We can also check that <code>Basilica</code> and <code>WRG</code> are contracting and compute their nuclei
<pre>
gap> IsContracting(Basilica);
true
gap> GroupNucleus(Basilica);
[ 1, u, v, u^-1, v^-1, u^-1*v, v^-1*u ]
gap> IsContracting( WRG );
true
gap> GroupNucleus( WRG );
[ 1, y*z^-1*x*y, z^-1*y^-1*x^-1*y*z^-1, z^-1*y^-1*x^-1, y^-1*x^-1*z*y^-1,
z*y^-1*x*y*z, x*y*z ]
</pre>
<p>
The group <code>GrigorchukGroup</code> is generated by a bounded automaton and, thus, is
amenable (see <a href="biblio.htm#BKNV05"><cite>BKNV05</cite></a>)
<pre>
gap> IsGeneratedByBoundedAutomaton(GrigorchukGroup);
true
gap> IsAmenable(GrigorchukGroup);
true
</pre>
<p>
We can compute the stabilizers of levels and vertices
<pre>
gap> StabilizerOfLevel(GrigorchukGroup, 2);
< a*b*a*d*a^-1*b^-1*a^-1, d, b*a*d*a^-1*b^-1, a*b*c*a^-1, b*a*b*a*b^-1*a^-1*b^
-1*a^-1, a*b*a*b*a*b^-1*a^-1*b^-1 >
gap> StabilizerOfVertex(GrigorchukGroup, [2, 1]);
< a*b*a*d*a^-1*b^-1*a^-1, d, a*c*b^-1*a^-1, c, b, a*b*a*c*a^-1*b^-1*a^
-1, a*b*a*b*a^-1*b^-1*a^-1 >
</pre>
<p>
In case of a finite group we can produce an isomorphism into a permutational group
<pre>
gap> f := IsomorphismPermGroup(Group(a,b));
[ a, b ] ->
[ (1,2)(3,5)(4,6)(7,9)(8,10)(11,13)(12,14)(15,17)(16,18)(19,21)(20,22)(23,
25)(24,26)(27,29)(28,30)(31,32), (1,3)(2,4)(5,7)(6,8)(9,11)(10,12)(13,
15)(14,16)(17,19)(18,20)(21,23)(22,24)(25,27)(26,28)(29,31)(30,32) ]
gap> Size(Image(f));
32
</pre>
<p>
Here is how to find relations in <code>Basilica</code> between elements of length not greater than 5.
<pre>
gap> FindGroupRelations(Basilica, 6);
v*u*v*u^-1*v^-1*u*v^-1*u^-1
v*u^2*v^-1*u^2*v*u^-2*v^-1*u^-2
v^2*u*v^2*u^-1*v^-2*u*v^-2*u^-1
[ v*u*v*u^-1*v^-1*u*v^-1*u^-1, v*u^2*v^-1*u^2*v*u^-2*v^-1*u^-2,
v^2*u*v^2*u^-1*v^-2*u*v^-2*u^-1 ]
</pre>
<p>
Or relations in the subgroup 〈<i>p</i>=<i>uv</i><sup>−1</sup>, <i>q</i>=<i>vu</i>〉
<pre>
gap> FindGroupRelations([u*v^-1,v*u], ["p", "q"], 5);
q*p^2*q*p^-1*q^-2*p^-1
[ q*p^2*q*p^-1*q^-2*p^-1 ]
</pre>
<p>
Or relations in the semigroup <code>SG</code>
<p>
<pre>
gap> FindSemigroupRelations(SG, 4);
f0^3 = f0
f0^2*f1 = f1
f1*f0^2 = f1
f1^3 = f1
[ [ f0^3, f0 ], [ f0^2*f1, f1 ], [ f1*f0^2, f1 ], [ f1^3, f1 ] ]
</pre>
<p>
Some basic operations with elements are the following:
<p>
The function <code>IsOne</code> computes whether an element represents the
trivial automorphism of the tree
<pre>
gap> IsOne( (a*b)^16 );
true
</pre>
<p>
Here is how to compute the order (this function might not stop in
some cases)
<pre>
gap> Order(a*b);
16
gap> Order(u^22*v^-15*u^2*v*u^10);
infinity
</pre>
<p>
One can check if a particular element acts spherically transitively on the tree
(this function might not stop in some cases)
<pre>
gap> IsSphericallyTransitive(a*b);
false
gap> IsSphericallyTransitive(u*v);
true
</pre>
<p>
The sections of an element can be obtained as follows
<pre>
gap> Section(u*v^2*u, 2);
u^2*v
gap> Decompose(u*v^2*u);
(v, u^2*v)
gap> Decompose(u*v^2*u, 3);
(v, 1, 1, 1, u*v, 1, u, 1)(1,2)(5,6)
</pre>
<p>
One can try to compute whether the elements of group <code>WRG</code> defined
by wreath recursion are finite-state and calculate corresponding
automaton
<p>
<pre>
gap> IsFiniteState(x*y^-1);
true
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 ]
gap> A := MealyAutomaton(x*y^-1);
<automaton>
gap> NumberOfStates(A);
15
</pre>
<p>
To get the action of an element on a vertex or on a particular level of the tree
use the following commands
<pre>
gap> [1,2,1,1]^(a*b);
[ 2, 2, 1, 1 ]
gap> PermOnLevel(u*v^2*v, 3);
(1,6,4,8,2,5,3,7)
</pre>
<p>
The action of the whole group <code>GrigorchukGroup</code> on some level can be computed via
<code>PermGroupOnLevel</code> (see <a href="CHAP002.htm#SSEC003.1">PermGroupOnLevel</a>).
<pre>
gap> PermGroupOnLevel(GrigorchukGroup, 3);
Group([ (1,5)(2,6)(3,7)(4,8), (1,3)(2,4)(5,6), (1,3)(2,4), (5,6) ])
gap> Size(last);
128
</pre>
<p>
The next example shows how to find all elements of Grigorchuk group of length at most 5, which have order 16.
<pre>
gap> FindElements(GrigorchukGroup, Order, 16, 5);
[ a*b, b*a, c*a*d, d*a*c, a*b*a*d, a*c*a*d, a*d*a*b, a*d*a*c, b*a*d*a,
c*a*d*a, d*a*b*a, d*a*c*a, a*c*a*d*a, a*d*a*c*a, b*a*b*a*c, b*a*c*a*c,
c*a*b*a*b, c*a*c*a*b ]
</pre>
<p>
<p>
[<a href = "chapters.htm">Up</a>] [<a href ="CHAP002.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<address>automgrp manual<br>September 2008
</address></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
576
