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