| Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/automgrp/doc/ (Algebra von RWTH Aachen Version 4.15.1©) Datei vom 8.0.2025 mit Größe 15 kB |
|
intro.tex
Interaktion und |
|||||||||
|
% This file was created automatically from intro.msk.
% DO NOT EDIT! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Chapter{Introduction} The `AutomGrp' package provides methods for computation with groups and semigroups generated by finite automata or given by wreath recursions, as well as with their finitely generated subgroups, subsemigroups and elements. 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 \cite{BGK32}), as well as many subsequent papers. First author thanks Sveta and Max Muntyan for their infinite patience and understanding. Second author thanks Olga, Anna, Irina and Andrey Savchuk for their help and understanding. This project would be impossible without them. 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 consta in the project. We also appreciate the code provided by Andrey Russev that was used to optimize the minimizatio Both authors were partially supported by NSF grants DMS-0600975, DMS-0456185 and DMS-030898 appreciates the support from the New Researcher Grant from University of South Florida and the Collaboration Grant from Simons Foundation. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Short math background} 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 to the theory of groups generated by automata we refer the reader to~\cite{GNS00}. The infinite connected tree with selected vertex, called the <root>, in which the degree of every vertex except the root is $d+1$ and the degree of the root is $d$ is called the <regular homogeneous rooted tree of degree $d$> (or <$d$-ary tree>). The rooted tree of degree $2$ is called the <binary tree>. The $n$-th <level> of the tree consists of all vertices located at distance $n$ from the root (here we mean combinatorial distance in the graph). Similarly one defines <spherically homogeneous> (or <spherically-transitive>) rooted trees as rooted trees, such that the degrees of all vertices at each level coincide (but may depend on the level). Given a finite alphabet $X=\{1,2,\ldots,d\}$ the set $X^{*}$ of all finite words over $X$ may be endowed with the structure of a $d$-ary tree in which the empty word $\emptyset$ is the <root>, the <level> $n$ in $X^{*}$ consists of the words of length $n$ over $X$ and every vertex $v$ has $d$ children, labeled by $vx$, for $x\in X$. Any automorphism $f$ of a rooted tree $T$ fixes the root and the levels. For any vertex $v$ of the tree $T$ each automorphism $f$ induces the automorphism $f|_v$ of the subtree of $T$ hanging down from the vertex $v$ by $f|_v(u)=w$ if $f(vu)=v'w$ for some $v'\in X^{|v|}$ from the same level as $v$ (here $|v|$ denotes the combinatorial distance from $v$ to the root of the tree). This automorphism is called the <section> of $f$ at $v$. If the tree $T$ is regular, then the subtrees hanging down from vertices of $T$ are canonically isomorphic to $T$ and, thus, the sections of any automorphism $f$ of $T$ can be considered as automorphisms of $T$ again. A group $G$ of automorphisms of a regular rooted tree $T$ is called <self-similar> if all sections of every element of $G$ belong to $G$. A self-similar group $G$ is called <contracting> if there is a finite set $N$ of elements of $G$, such that for any $g$ in $G$ there is a level $n$ such that all sections of $g$ at vertices of levels bigger than $n$ belong to $N$. The smallest set with such a property is called the <nucleus> of $G$. Any automorphism $f$ of a rooted tree can be decomposed as $$f=(f_1,f_2,\ldots,f_d)\sigma,$$ where $f_1,\ldots,f_d$ are the sections of $f$ at the vertices of the first level and $\sigma$ is the permutation which permutes the subtrees hanging down from these vertices. This notation is very convenient for performing multiplication of elements. Throughout this manual and everywhere in the package we use the right action of (semi)groups acting on trees and for automorphisms (homomorphisms) of a tree $f$ and $g$, the composition $f.g$ means that $f$ acts first. This is consistent with the order of multiplication of permutations in \GAP\ , even though some authors in the field prefer to use the left action. With this convention in mind, If $f=(f_1,f_2,\ldots,f_d)\sigma$ and $g=(g_1,g_2,\ldots,g_d)\pi$, then $$f.g=(f_1.g_{\sigma(1)},\ldots,f_d.g_{\sigma(d)})\sigma\pi,$$ $$f^{-1}=(f_{\sigma^{-1}(1)}^{-1},\ldots,f_{\sigma^{-1}(d)}^{-1})\sigma^{-1}\.$$ The group of automorphisms of a rooted tree is said to be <level-transitive> if it acts transitively on each level of the tree. 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. A special class of self-similar groups is the class of groups generated by finite automata. This class is especially nice from the algorithmic point of view. Let us recall basic definitions. A <Mealy automaton> (<transducer>, <synchronous automaton>, or, simply, <automaton>) is a tuple $A=(Q,X,\rho,\tau)$, where $Q$ is a set of <states>, $X$ is a finite <alphabet> of cardinality $d \geq 2$, $\rho:Q \times X \to X$ is a map, called the <output map>, $\tau:Q \times X \to Q$ is a map, called the <transition map>. If for each state $q$ in $Q$, the restriction $\rho_q: X \to X$ given by $\rho_q(x)=\rho(q,x)$ is a permutation, the automaton is called <invertible>. If the set $Q$ of states is finite, the automaton is called <finite>. If some state $q$ in $Q$ of the automaton $A$ is selected to be initial, the automaton is called <initial> and denoted $A_q$. If an initial state is not specified, the automaton is called <noninitial>. An initial automaton naturally acts on $X^{*}$ by homomorphisms (automorphisms in the case of an invertible automation) in the following way. Given a word $x_1x_2\ldots x_n$, the automaton starts at the initial state $q$, reads the first input letter $x_1$, outputs the letter $\rho_q(x_1)$ and changes its state to $q_1=\tau(q,x_1)$. The rest of the input word is handled by the new state $q_1$ in the same way. Formally speaking, the functions $\rho$ and $\tau$ can be extended to $\rho\colon Q \times X^{*} \to X^{*}$ and $\tau\colon Q \times X^{*} \to Q$. Given an automaton $A$ the group $G(A)$ of automorphisms of $X^{*}$ generated by all the states of $A$ (as initial automata) is called the <automaton group> defined by $A$. Every automaton group is self-similar, because the section of $A_q$ at vertex $v$ is just $A_{\tau(q,v)}$. 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 the computational point of view. Finite automata are often described by <recursive relations> (or <wreath recursion>) of the form $$q=(\tau(q,1),\ldots,\tau(q,d)) \rho_q$$ for every state $q$. For example, the line $a=(a,b)(1,2), b=(a,b)$ describes the automaton with 2 states $a$ and $b$, such that $a$ permutes the letters $1$ and $2$ of the alphabet $X=\{1,2\}$ and $b$ does not; and, independently of the current state, the automaton changes its initial state to $a$ if it reads $1$ and to $b$ if it reads $2$. This particular automaton generates the, so-called, lamplighter group. Semigroups generated by noninvertible automata are defined in a similar way. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Installation instructions} `AutomGrp' package requires \GAP\ version at least 4.4.6 and `FGA' (Free Group Algorithms) package available at \URL{https://www.gap-system.org/Packages/fga.h The installation of the `AutomGrp' package follows the standard \GAP\ rules, i.e. to install it unpack the archive into the `pkg' directory of your \GAP\ distribution. This will create `automgrp' subdirectory. % Use `automgrp-1.3.3-win.zip' archive if you are installing on % a Microsoft Windows system, and `automgrp-1.3.3.tar.bz2' or % `automgrp-1.3.3.tar.gz' otherwise. To load package issue the command \beginexample gap> LoadPackage("automgrp"); ---------------------------------------------------------------- Loading AutomGrp 1.3 (Automata Groups and Semigroups) by Yevgen Muntyan (muntyan@fastmail.fm) Dmytro Savchuk (http://savchuk.myweb.usf.edu/) Homepage: https://gap-packages.github.io/automgrp/ ---------------------------------------------------------------- true \endexample Note, that if the `FR' package by Laurent Bartholdi is installed as well, \GAP\ will automatically load it, together with the packages on which it depends. The `FR' package functionality partially overlaps with the one of `AutomGrp'. For the user's convenience and to expand the functionality of both packages, several con and `FR2AutomGrp' ("FR2AutomGrp")) of the basic data types were implemented in `A To test the installation, issue the command \beginexample gap> Read( Filename( DirectoriesPackageLibrary( "automgrp", "tst" ), "testall.g")); \endexample in the \GAP\ command line. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Quick example} Here is how to define the Grigorchuk group and Basilica group. \beginexample gap> Grigorchuk_Group := 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 > \endexample 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 (\cite{BRS06}) \beginexample gap> SG := AutomatonSemigroup( "f0=(f0,f0)(1,2), f1=(f1,f0)[2,2]" ); < f0, f1 > \endexample Another type of groups (semigroups) implemented in the package is the class of groups (semigroups) defined by wreath recursion (finitely generated self-similar groups). \beginexample gap> WRG := SelfSimilarGroup("x=(1,y)(1,2),y=(z^-1,1)(1,2),z=(1,x*y)"); < x, y, z > \endexample Now we can compute several properties of `Grigorchuk_Group', `Basilica' and `SG' \beginexample gap> IsFinite(Grigorchuk_Group); false gap> IsSphericallyTransitive(Grigorchuk_Group); true gap> IsFractal(Grigorchuk_Group); true gap> IsAbelian(Grigorchuk_Group); false gap> IsTransitiveOnLevel(Grigorchuk_Group, 4); true \endexample We can also check that `Basilica' and `WRG' are contracting and compute their nuclei \beginexample 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 ] \endexample The group `Grigorchuk_Group' is generated by a bounded automaton and, thus, is amenable (see \cite{BKNV05}) \beginexample gap> IsGeneratedByBoundedAutomaton(Grigorchuk_Group); true gap> IsAmenable(Grigorchuk_Group); true \endexample We can compute the stabilizers of levels and vertices \beginexample gap> StabilizerOfLevel(Grigorchuk_Group, 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(Grigorchuk_Group, [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 > \endexample In the case of a finite group we can produce an isomorphism into a permutation group \beginexample 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 \endexample Here is how to find relations in `Basilica' between elements of length not greater than \beginexample 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 ] \endexample Or relations in the subgroup $\langle p=uv^{-1}, q=vu\rangle$ \beginexample 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 ] \endexample Or relations in the semigroup `SG' \beginexample 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 ] ] \endexample Some basic operations with elements are the following: The function `IsOne' computes whether an element represents the trivial automorphism of the tree \beginexample gap> IsOne( (a*b)^16 ); true \endexample Here is how to compute the order (this function might not stop in some cases) \beginexample gap> Order(a*b); 16 gap> Order(u^22*v^-15*u^2*v*u^10); infinity \endexample Note that the package contains many helpful notifications that can be enabled by changing `InfoLevel' for `InfoAutomGrp'. In many situations level 3 provides additional information about the computation that can be used either to track the progress or to extract the proof from the result as it can be done in the example below. \beginexample gap> SetInfoLevel(InfoAutomGrp,3); gap> Order(u^22*v^-15*u^2*v*u^10); #I v is obtained from (u^22*v^-15*u^2*v*u^10)^1 by taking sections and cyclic reductions at vertex [ 1, 1, 1, 1, 1, 1, 1, 1, 1 ] #I v is obtained from (v)^2 by taking sections and cyclic reductions at vertex [ 1, 1 ] infinity \endexample One can check if a particular element acts spherically transitively on the tree (this function might not stop in some cases) \beginexample gap> IsSphericallyTransitive(a*b); false gap> IsSphericallyTransitive(u*v); true \endexample The sections of an element can be obtained as follows \beginexample 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) \endexample One can try to compute whether the elements of group `WRG' defined by wreath recursion are finite-state and calculate corresponding automaton \beginexample 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 \endexample To get the action of an element on a vertex or on a particular level of the tree use the following commands \beginexample 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) \endexample The action of the whole group `Grigorchuk_Group' on some level can be computed via `PermGroupOnLevel' (see "PermGroupOnLevel"). \beginexample gap> PermGroupOnLevel(Grigorchuk_Group, 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 \endexample The next example shows how to find all elements of length at most 5 of order 16 in the Grigorchuk gr \beginexample gap> FindElements(Grigorchuk_Group, 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 ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.45Angebot Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können ¤*Eine klare Vorstellung vom Zielzustand |
|
2026-03-28