1############################################################################# 2## 3#W automgroup.gd automgrp package Yevgen Muntyan 4#W Dmytro Savchuk 5## 6#Y Copyright (C) 2003 - 2018 Yevgen Muntyan, Dmytro Savchuk 7## 8 9 10############################################################################# 11## 12#C IsAutomGroup( <G> ) 13## 14## The category of groups generated by finite invertible initial automata 15## (elements from category `IsAutom'). 16## 17DeclareSynonym("IsAutomGroup", IsAutomCollection and IsGroup); 18InstallTrueMethod(IsTreeAutomorphismCollection, IsAutomGroup); 19InstallTrueMethod(IsInvertibleAutomCollection, IsAutomGroup); 20 21 22############################################################################# 23## 24#O AutomatonGroup( <string>[, <bind_vars>] ) 25#O AutomatonGroup( <list>[, <names>, <bind_vars>] ) 26#O AutomatonGroup( <automaton>[, <bind_vars>] ) 27## 28## Creates the self-similar group generated by the finite automaton, described by <string> 29## or <list>, or by the argument <automaton>. 30## 31## The argument <string> is a conventional notation of the form 32## `name1=(name11,name12,...,name1d)perm1, name2=...' 33## where each `name\*' is a name of a state or `1', and each `perm\*' is a 34## permutation written in {\GAP} notation. Trivial permutations may be 35## omitted. This function ignores whitespace, and states may be separated 36## by commas or semicolons. 37## 38## The argument <list> is a list consisting of $n$ entries corresponding to $n$ states of an automaton. 39## Each entry is of the form $[a_1,\.\.\.,a_d,p]$, 40## where $d \geq 2$ is the size of the alphabet the group acts on, $a_i$ are `IsInt' in 41## $\{1,\ldots,n\}$ and 42## represent the sections of the corresponding state at all vertices of the first level of the tree; 43## and $p$ from `SymmetricGroup(<d>)' describes the action of the corresponding state on the 44## alphabet. 45## 46## The optional argument <names> must be a list of names of generators of the group, corresponding to the 47## states of the automaton. 48## These names are used to display elements of the resulting group. 49## 50## If the optional argument <bind_vars> is `false' the names of generators of the group are not assigned 51## to the global variables. The default value is `true'. One can use 52## `AssignGeneratorVariables' function to assign these names later, if they were not assigned 53## when the group was created. 54## 55## \beginexample 56## gap> AutomatonGroup("a=(a,b), b=(a, b)(1,2)"); 57## < a, b > 58## gap> AutomatonGroup("a=(b,a,1)(2,3), b=(1,a,b)(1,2,3)"); 59## < a, b > 60## gap> A := MealyAutomaton("a=(b,1)(1,2), b=(a,1)"); 61## <automaton> 62## gap> G := AutomatonGroup(A); 63## < a, b > 64## \endexample 65## 66## In the second form of this operation the definition of the first group 67## looks like 68## \beginexample 69## gap> AutomatonGroup([ [ 1, 2, ()], [ 1, 2, (1,2) ] ], [ "a", "b" ]); 70## < a, b > 71## \endexample 72## 73DeclareOperation("AutomatonGroup", [IsList]); 74DeclareOperation("AutomatonGroup", [IsMealyAutomaton]); 75DeclareOperation("AutomatonGroup", [IsList, IsList]); 76DeclareOperation("AutomatonGroup", [IsList, IsBool]); 77DeclareOperation("AutomatonGroup", [IsMealyAutomaton, IsBool]); 78DeclareOperation("AutomatonGroup", [IsList, IsList, IsBool]); 79 80 81############################################################################# 82## 83#P IsGroupOfAutomFamily( <G> ) 84## 85## Whether group <G> is the whole group generated by the automaton used to 86## construct elements of <G>. 87## 88DeclareProperty("IsGroupOfAutomFamily", IsAutomGroup); 89InstallTrueMethod(IsSelfSimilar, IsGroupOfAutomFamily); 90 91 92 93############################################################################# 94## 95#A UnderlyingFreeSubgroup( <G> ) 96## 97DeclareAttribute("UnderlyingFreeSubgroup", IsAutomGroup, "mutable"); 98 99 100############################################################################# 101## 102#P IsAutomatonGroup( <G> ) 103## 104## is `true' if <G> is created using the command `AutomatonGroup' ("AutomatonGroup") 105## or if the generators of <G> coincide with the generators of the corresponding family, and `false' otherwise. 106## To test whether <G> is self-similar use `IsSelfSimilar' ("IsSelfSimilar") command. 107## 108DeclareProperty("IsAutomatonGroup", IsAutomGroup); 109InstallTrueMethod(IsGroupOfAutomFamily, IsAutomatonGroup); 110 111 112############################################################################# 113## 114#A MihailovaSystem( <G> ) 115## 116## In the case when <G> is an automaton fractal group acting on a binary 117## tree, computes the generating set for the first level stabilizer in G 118## such that the sections of these generators at the first level, 119## viewed as elements of $F_r\times F_r$, are in Mihailova normal form. 120## See~\cite{GSESS} for details. 121## 122## \beginexample 123## gap> G := AutomatonGroup("a=(b,c)(1,2),b=(a,c),c=(a,a)"); 124## < a, b, c > 125## gap> M := MihailovaSystem(G); 126## [ c^-1*b, c^-1*b^-1*c*a^-1*b*c*b^-1*a, a^-1*b*c*b^-1*a, a*c^-1*b^-1*a*c, 127## c^-1*a^-1*b*c*a ] 128## gap> for g in M do 129## > Print(g,"=",Decompose(g),"\n"); 130## > od; 131## c^-1*b=(1, a^-1*c) 132## c^-1*b^-1*c*a^-1*b*c*b^-1*a=(1, a^-1*c^-1*a*b^-1*a*b) 133## a^-1*b*c*b^-1*a=(a, b^-1*a*b) 134## a*c^-1*b^-1*a*c=(b, c*a^-2*b*a) 135## c^-1*a^-1*b*c*a=(c, a^-1*b^-1*a^2*b) 136## \endexample 137## 138DeclareAttribute("MihailovaSystem", IsAutomatonGroup, "mutable"); 139 140 141############################################################################# 142## 143#A GroupOfAutomFamily(<G>) 144## 145 146DeclareAttribute("GroupOfAutomFamily", IsAutomGroup); 147 148#E 149