At the core of this package are functionally recursive machines. The internals of specific machines will be described later, but each machine \(M\) has an associated alphabet \(X\), a set of states \(Q\), and a transition function \(\phi:Q \times X \to X \times Q\). An element, as we will see in Section 4, is given by a machine and an initial state \(q\in Q\).
The element \((M,q)\) defines a transformation on the set \(X^*\) of strings (finite or infinite) over the alphabet \(X\), as follows: the empty string is always fixed. Given a string \(x_1x_2\ldots x_n\) with \(n\ge0\), compute \(\phi(q,x_1)=(y_1,r)\); then compute the action of \((M,r)\) on the string \(x_2\ldots x_n\), and call the result \(y_2\ldots y_n\). Then the action of \((M,q)\) on \(x_1x_2\ldots x_n\) yields \(y_1y_2\ldots y_n\).
This can be understood more formally as follows. The transition function \(\phi\) induces a map \(\phi^n:Q\times X^n \to X^n \times Q\), defined by successively applying \(\phi\) to move the \(Q\) from the left to the right. Similarly, \(\phi\) can be extended to a map \(Q^m\times X^n \to X^n \times Q^m\).
We see that the action on finite strings preserves their length, and also preserves prefixes: if \((M,q)\) maps \(x_1\ldots x_n\) to \(y_1\ldots y_m\), then necessarily \(m=n\); and if \(k<n\) then \(T\) maps \(x_1\ldots x_k\) to \(y_1\ldots y_k\).
The strings over the alphabet \(X\) can be naturally organised into a rooted tree. The root represents the empty string, and the strings \(x_1\ldots x_n\) and \(x_1\ldots x_{n+1}\) are connected by an edge, for all \(x_i\in X\).
Machines must be accessible to computation; therefore it is reasonable to assume that their alphabet \(X\) is finite.
If the stateset \(Q\) is also finite, the machine is called a Mealy machine, and its transition function \(\phi\) can be stored as a table.
More general machines are obtained if one allows the stateset \(Q\) to be a free group/semigroup/monoid generated by a finite set \(S\), and the transition function \(\phi\) to be specified on \(S\times X\). Its values are then extended naturally by composition.
Machines store their transitions (second coordinate of \(\phi\)), and their output, (first coordinate of \(\phi\)) in a matrix indexed by state and letter. In particular, PermList(output[state]) gives the action on the first level.
Because of the way GAP handles permutations and transformations, a permutation is never equal to a transformation, even though both can answer true to \(IsOne\). Therefore, FR stores the output as a list, which can be then accessed (e.g. in commands such as ActivityPerm and ActivityTransformation either as a permutation or as a transformation. The command Activity itself will return a permutation if possible, and otherwise a transformation.
Machines can be combined in different manners. If two machines act on the same alphabet, then their sum and product are defined as machines acting again on the same alphabet; the statesets are the free products (which is also their sum, in the category of semigroups) of the respective statesets. The sum or product of machines has a stateset of highest possible category, i.e. is a group unless some argument is a monoid, and a monoid unless some argument is a semigroup. The transition and output functions are the union of the respective functions of their arguments.
If a non-empty collection of machines have same stateset, then their tensor sum and tensor product are machines again with same stateset; the alphabets on which the machines act are the disjoint union, respectively cartesian product, of the arguments' alphabets. The transition and output functions are again the union or composition of the respective functions of their arguments.
The direct sum and direct product of a collection of machines are always defined. Its stateset is generated by the union of the arguments' statesets, as for a sum or a product; its alphabet is the disjoint union, respectively cartesian product of its arguments' alphabets, as for a tensor sum or product. The transition and output functions are again the union of the respective functions of their arguments.
FRMachines‣ FRMachineNC( fam, free, transitions, outputs ) | ( operation ) |
Returns: A new FR machine.
This function constructs a new FR machine, belonging to family fam. It has stateset the free group/semigroup/monoid free, and transitions described by states and outputs.
transitions is a list of lists; transitions[s][x] is a word in free, which is the state reached by the machine when started in state s and fed input x.
outputs is also a list of lists; outputs[s][x] is the output produced by the machine is in state s and inputs x.
gap> f := FreeGroup(2); <free group on the generators [ f1, f2 ]> gap> m := FRMachineNC(FRMFamily([1,2]),f,[[One(f),f.1],[One(f),f.2^-1]], [[2,1],[1,2]]); <FR machine with alphabet [ 1, 2 ] on Group( [ f1, f2 ] )>
‣ FRMachine( [names, ]transitions, outputs ) | ( operation ) |
‣ FRMachine( free, transitions, outputs ) | ( operation ) |
Returns: A new FR machine.
This function constructs a new FR machine. It has stateset a free group/semigroup/monoid, and structure described by transitions and outputs.
If there is an argument free, it is the free group/monoid/semigroup to be used as stateset. Otherwise, the stateset will be guessed from the transitions and outputs; it will be a free group if all states are invertible, and a monoid otherwise. names is then an optional list, with at position s a string naming generator s of the stateset. If names contains too few entries, they are completed by the names __1,__2,....
transitions is a list of lists; transitions[s][x] is either an associative word, or a list of integers describing the state reached by the machine when started in state s and fed input x. Positive integers indicate a generator index, negative integers its inverse, the empty list in the identity state, and lists of length greater than one indicate a product of states. If an entry is an FR element, then its machine is incorporated into the newly constructed one.
outputs is a list; at position s it contains a permutation, a transformation, or a list of integers (the images of a transformation), describing the activity of state s. If all states are invertible, the outputs are all converted to permutations, while if there is a non-invertible state then the outputs are all converted to transformations.
gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]); <FR machine with alphabet [ 1, 2 ] on Group( [ tau, mu ] )> gap> m=n; true gap> Display(n); | 1 2 -----+--------+---------+ tau | <id>,2 tau,1 mu | <id>,2 mu^-1,1 -----+--------+---------+ gap> m := FRMachine([[[],[FRElement(n,1)]]],[()]); <FR machine with alphabet [ 1, 2 ] on Group( [ f1, f2, f3 ] )> gap> Display(m); | 1 2 ----+--------+---------+ f1 | <id>,1 f2,2 f2 | <id>,2 f2,1 f3 | <id>,2 f1^-1,1 ----+--------+---------+ gap> f := FreeGroup(2); <free group on the generators [ f1, f2 ]> gap> p := FRMachine(f,[[One(f),f.1],[One(f),f.2^-1],[(1,2),(1,2)]); <FR machine with alphabet [ 1, 2 ] on Group( [ f1, f2 ] )> gap> n=p; true
‣ UnderlyingFRMachine( obj ) | ( attribute ) |
Returns: An FR machine underlying obj.
FR elements, FR groups etc. often have an underlying FR machine, which is returned by this command.
gap> m := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]); <FR machine with alphabet [ 1, 2 ] on Group( [ a, b ] )> gap> a := FRElement(m,1); b := FRElement(m,2); <2|a> <2|b> gap> UnderlyingFRMachine(a)=m; true
‣ AsGroupFRMachine( m ) | ( attribute ) |
‣ AsMonoidFRMachine( m ) | ( attribute ) |
‣ AsSemigroupFRMachine( m ) | ( attribute ) |
Returns: An FR machine isomorphic to m, on a free group/monoid/semigroup.
This function constructs, from the FR machine m, an isomorphic FR machine n with a free group/monoid/semigroup as stateset. The attribute Correspondence(n) is a mapping (homomorphism or list) from the stateset of m to the stateset of n.
m can be an arbitrary FR machine, or can be an free group/monoid/semigroup endomorphism. It is then converted to an FR machine on a 1-letter alphabet.
gap> s := FreeSemigroup(1);; gap> sm := FRMachine(s,[[GeneratorsOfSemigroup(s)[1], GeneratorsOfSemigroup(s)[1]^2]],[(1,2)]); <FR machine with alphabet [ 1, 2 ] on Semigroup( [ s1 ] )> gap> m := FreeMonoid(1);; gap> mm := FRMachine(m,[[One(m),GeneratorsOfMonoid(m)[1]^2]],[(1,2)]); <FR machine with alphabet [ 1, 2 ] on Monoid( [ m1 ], ... )> gap> g := FreeGroup(1);; gap> gm := FRMachine(g,[[One(g),GeneratorsOfGroup(g)[1]^-2]],[(1,2)]); <FR machine with alphabet [ 1, 2 ] on Group( [ f1 ] )> gap> AsGroupFRMachine(sm); Display(last); <FR machine with alphabet [ 1, 2 ] on Group( [ f1 ] )> | 1 2 ----+------+--------+ f1 | f1,2 f1^2,1 ----+------+--------+ gap> Correspondence(last); MappingByFunction( <free semigroup on the generators [ s1 ]>, <free group on the generators [ f1 ]>, function( w ) ... end ) gap> AsGroupFRMachine(mm); Display(last); <FR machine with alphabet [ 1, 2 ] on Group( [ f1 ] )> | 1 2 ----+--------+--------+ f1 | <id>,2 f1^2,1 ----+--------+--------+ gap> AsGroupFRMachine(gm); Display(last); <FR machine with alphabet [ 1, 2 ] on Group( [ f1 ] )> | 1 2 ----+--------+---------+ f1 | <id>,2 f1^-2,1 ----+--------+---------+ gap> AsMonoidFRMachine(sm); Display(last); <FR machine with alphabet [ 1, 2 ] on Monoid( [ m1 ], ... )> | 1 2 ----+------+--------+ m1 | m1,2 m1^2,1 ----+------+--------+ gap> AsMonoidFRMachine(mm); Display(last); <FR machine with alphabet [ 1, 2 ] on Monoid( [ m1 ], ... )> | 1 2 ----+--------+--------+ m1 | <id>,2 m1^2,1 ----+--------+--------+ gap> AsMonoidFRMachine(gm); Display(last); <FR machine with alphabet [ 1, 2 ] on Monoid( [ m1, m2 ], ... )> | 1 2 ----+--------+--------+ m1 | <id>,2 m2^2,1 m2 | m1^2,2 <id>,1 ----+--------+--------+ gap> AsSemigroupFRMachine(sm); Display(last); <FR machine with alphabet [ 1, 2 ] on Semigroup( [ s1 ] )> | 1 2 ----+------+--------+ s1 | s1,2 s1^2,1 ----+------+--------+ gap> AsSemigroupFRMachine(mm); Display(last); <FR machine with alphabet [ 1, 2 ] on Semigroup( [ s1, s2 ] )> | 1 2 ----+------+--------+ s1 | s2,2 s1^2,1 s2 | s2,1 s2,2 ----+------+--------+ gap> AsSemigroupFRMachine(gm); Display(last); <FR machine with alphabet [ 1, 2 ] on Semigroup( [ s1, s2, s3 ] )> | 1 2 ----+--------+--------+ s1 | s3,2 s2^2,1 s2 | s1^2,2 s3,1 s3 | s3,1 s3,2 ----+--------+--------+ gap> gap> Display(GuptaSidkiMachines(3)); | 1 2 3 ---+-----+-----+-----+ a | a,1 a,2 a,3 b | a,2 a,3 a,1 c | a,3 a,1 a,2 d | b,1 c,2 d,3 ---+-----+-----+-----+ gap> AsGroupFRMachine(GuptaSidkiMachines(3)); <FR machine with alphabet [ 1 .. 3 ] on Group( [ f1, f2 ] )> gap> Display(last); | 1 2 3 ----+--------+---------+--------+ f1 | <id>,2 <id>,3 <id>,1 f2 | f1,1 f1^-1,2 f2,3 ----+--------+---------+--------+ gap> Correspondence(last); [ <identity ...>, f1, f1^-1, f2 ] gap> AsGroupFRMachine(GroupHomomorphism(g,g,[g.1],[g.1^3])); <FR machine with alphabet [ 1 ] on Group( [ f1 ] )> gap> Display(last); G | 1 ----+--------+ f1 | f1^3,1 ----+--------+
‣ AsGroupFRMachine( f ) | ( attribute ) |
‣ AsMonoidFRMachine( f ) | ( attribute ) |
‣ AsSemigroupFRMachine( f ) | ( attribute ) |
Returns: An FR machine.
This function creates an FR machine on a 1-letter alphabet, that represents the endomorphism f. It is specially useful when combined with products of machines; indeed the usual product of machines corresponds to composition of endomorphisms.
gap> f := FreeGroup(2);; gap> h := GroupHomomorphismByImages(f,f,[f.1,f.2],[f.2,f.1*f.2]); [ f1, f2 ] -> [ f2, f1*f2 ] gap> m := AsGroupFRMachine(h); <FR machine with alphabet [ 1 ] on Group( [ f1, f2 ] )> gap> mm := TensorProduct(m,m); <FR machine with alphabet [ 1 ] on Group( [ f1, f2 ] )> gap> Display(mm); G | 1 ----+------------+ f1 | f1*f2,1 f2 | f2*f1*f2,1 ----+------------+
FRMachines‣ StateSet( m ) | ( attribute ) |
Returns: The set of states associated with m.
This function returns the stateset of m. It can be either a list (if the machine is of Mealy type), or a free group/semigroup/monoid (in all other cases).
gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]); <FR machine with alphabet [ 1, 2 ] on Group( [ tau, mu ] )> gap> StateSet(n); <free group on the generators [ tau, mu ]> gap> StateSet(AsMealyMachine(n)); [ 1 .. 4 ]
‣ GeneratorsOfFRMachine( m ) | ( attribute ) |
Returns: The generating set of the stateset of m.
This function returns the generating set of the stateset of m. If m is a Mealy machine, it returs the stateset.
gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]); <FR machine with alphabet [ 1, 2 ] on Group( [ tau, mu ] )> gap> GeneratorsOfFRMachine(n); [ tau, mu ]
‣ Output( m ) | ( operation ) |
‣ Output( m, s ) | ( operation ) |
‣ Output( m, s, x ) | ( operation ) |
Returns: A transformation of m's alphabet.
In the first form, this function returns the output of m.
In the second form, this function returns the transformation of m's alphabet associated with state s. This transformation is returned as a list of images.
s is also allowed to be a list, in which case it is interpreted as the corresponding product of states.
In the third form, the result is actually the image of x under Output(m,s).
gap> n := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]); <FR machine with alphabet [ 1, 2 ] on Group( [ a, b ] )> gap> Output(n,[1,2]); [2,1] gap> Output(n,Product(GeneratorsOfFRMachine(n))); [2,1]
‣ Transition( m, s, i ) | ( operation ) |
Returns: An element of m's stateset.
This function returns the state reached by m when started in state s and fed input i. This input may be an alphabet letter or a sequence of alphabet letters.
gap> n := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]); <FR machine with alphabet [ 1, 2 ] on Group( [ a, b ] )> gap> Transition(n,[2,1],2); a*b gap> Transition(n,Product(GeneratorsOfFRMachine(n))^2,1); a*b
‣ Transitions( m, s ) | ( operation ) |
Returns: A list of elements of m's stateset.
This function returns the states reached by m when started in state s and fed inputs from the alphabet. The state may be expressed as a word or as a list of states.
gap> n := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]); <FR machine with alphabet [ 1, 2 ] on Group( [ a, b ] )> gap> Transitions(n,[2,1]); [ <identity ...>, a*b ] gap> Transitions(n,Product(GeneratorsOfFRMachine(n))^2); [ a*b, b*a ]
‣ WreathRecursion( m ) | ( attribute ) |
Returns: A function on the stateset of m.
This function returns a function on m's stateset. This function, on receiving state q as input, returns a list. Its first entry is a list indexed by m's alphabet, with in position x the state m would be in if it received input x when in state q. The second entry is the list of the permutation of m's alphabet induced by q.
WreathRecursion(machine)(q)[1][a] is equal to Transition(machine,q,a) and WreathRecursion(machine)(q)[2] is equal to Output(machine,q).
gap> n := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]); <FR machine with alphabet [ 1, 2 ] on Group( [ a, b ] )> gap> WreathRecursion(n)(GeneratorsOfFRMachine(n)[1]); [ [ <identity ...>, b ], [2,1] ] gap> WreathRecursion(n)(GeneratorsOfFRMachine(n)[2]); [ [ <identity ...>, a ], [1,2] ]
FRMachines‣ StructuralGroup( m ) | ( operation ) |
‣ StructuralMonoid( m ) | ( operation ) |
‣ StructuralSemigroup( m ) | ( operation ) |
Returns: A finitely presented group/monoid/semigroup capturing the structure of m.
This function returns a finitely presented group/monoid/semigroup, with generators the union of the AlphabetOfFRObject (10.1-3) and GeneratorsOfFRMachine (3.4-2) of m, and relations all \(qa'=aq'\) whenever \(\phi(q,a)=(a',q')\).
gap> n := FRMachine(["a","b","c"],[[[2],[3]],[[3],[2]],[[1],[1]]],[(1,2),(1,2),()]); <FR machine with alphabet [ 1, 2 ] on Group( [ a, b, c ] )> gap> StructuralGroup(n); <fp group on the generators [ a, b, c, 1, 2 ]> gap> RelatorsOfFpGroup(last); [ a*2*b^-1*1^-1, a*1*c^-1*2^-1, b*2*c^-1*1^-1, b*1*b^-1*2^-1, c*1*a^-1*1^-1, c*2*a^-1*2^-1 ] gap> SimplifiedFpGroup(last2); <fp group on the generators [ a, 1 ]> gap> RelatorsOfFpGroup(last); [ 1^-1*a^2*1^4*a^-2*1^-1*a*1^-2*a^-1, 1*a*1^-1*a*1^2*a^-1*1*a^-2*1^-3*a, 1^-1*a^2*1^2*a^-1*1^-1*a*1^2*a^-2*1^-2 ]
3.5-2 \+‣ \+( m1, m2 ) | ( method ) |
Returns: A new FR machine, in the same family as its arguments.
This function returns a new FR machine r, with stateset generated by the union of the statesets of its arguments. The arguments m1 and m2 must operate on the same alphabet. If the stateset of m1 is free on \(n_1\) letters and the stateset of m2 is free on \(n_2\) letters, then the stateset of their sum is free on \(n_1+n_2\) letters, with the first \(n_1\) identified with m1's states and the next \(n_2\) with m2's.
The transition and output functions are naturally extended to the sum.
The arguments may be free group, semigroup or monoid machines. The sum is in the weakest containing category: it is a group machine if both arguments are group machines; a monoid if both are either group of monoid machines; and a semigroup machine otherwise.
The maps from the stateset of m1 and m2 to the stateset of r can be recovered as Correspondence(r)[1] and Correspondence(r)[2]; see Correspondence (3.5-12).
gap> tau := FRMachine([[[],[1]]],[(1,2)]); <FR machine with alphabet [ 1, 2 ] on Group( [ f1 ] )> gap> mu := FRMachine([[[],[-1]]],[(1,2)]); <FR machine with alphabet [ 1, 2 ] on Group( [ f1 ] )> gap> sum := tau+mu;; Display(sum); | 1 2 -----+--------+----------+ f11 | <id>,2 f11,1 f12 | <id>,2 f12^-1,1 -----+--------+----------+ gap> Correspondence(sum)[1]; [ f1 ] -> [ f11 ] gap> GeneratorsOfFRMachine(tau)[1]^last; f11
3.5-3 \*‣ \*( machine1, machine2 ) | ( method ) |
Returns: A new FR machine, in the same family as its arguments.
The product of two FR machines coincides with their sum, since the natural free object mapping to the product of the statesets is generated by the union of the statesets. See therefore \+ (3.5-2).
‣ TensorSumOp( FR_machines, machine ) | ( method ) |
Returns: A new FR machine on the disjoint union of the arguments' alphabets.
The tensor sum of FR machines with same stateset is defined as the FR machine acting on the disjoint union of the alphabets; if these alphabets are [1..n1] up to [1..nk], then the alphabet of their sum is [1..n1+...+nk] and the transition functions are similarly concatenated.
The first argument is a list; the second argument is any element of that list, and is used only to improve the method selection algorithm.
gap> m := TensorSum(AddingMachine(2),AddingMachine(3),AddingMachine(4)); AddingMachine(2)(+)AddingMachine(3)(+)AddingMachine(4) gap> Display(m); | 1 2 3 4 5 6 7 8 9 ---+-----+-----+-----+-----+-----+-----+-----+-----+-----+ a | a,1 a,2 a,3 a,4 a,5 a,6 a,7 a,8 a,9 b | a,2 b,1 a,4 a,5 b,3 a,7 a,8 a,9 b,6 ---+-----+-----+-----+-----+-----+-----+-----+-----+-----+
‣ TensorProductOp( FR, machines, machine ) | ( method ) |
Returns: A new FR machine on the cartesian product of the arguments' alphabets.
The tensor product of FR machines with same stateset is defined as the FR machine acting on the cartesian product of the alphabets. The transition function and output function behave as if a single letter, in the tensor product's alphabet, were a word (read from left to right) in the machines' alphabets.
The first argument is a list; the second argument is any element of that list, and is used only to improve the method selection algorithm.
gap> m := TensorProduct(AddingMachine(2),AddingMachine(3)); AddingMachine(2)(*)AddingMachine(3) gap> Display(last); | 1 2 3 4 5 6 ---+-----+-----+-----+-----+-----+-----+ a | a,1 a,2 a,3 a,4 a,5 a,6 b | a,4 a,5 a,6 a,2 a,3 b,1 ---+-----+-----+-----+-----+-----+-----+
‣ DirectSumOp( FR, machines, machine ) | ( method ) |
Returns: A new FR machine on the disjoint union of the arguments' alphabets.
The direct sum of FR machines is defined as the FR machine with stateset generated by the disjoint union of the statesets, acting on the disjoint union of the alphabets; if these alphabets are [1..n1] up to [1..nk], then the alphabet of their sum is [1..n1+...+nk] and the output and transition functions are similarly concatenated.
The first argument is a list; the second argument is any element of that list, and is used only to improve the method selection algorithm.
gap> m := DirectSum(AddingMachine(2),AddingMachine(3),AddingMachine(4)); AddingMachine(2)#AddingMachine(3)#AddingMachine(4) gap> Display(m); | 1 2 3 4 5 6 7 8 9 ---+-----+-----+-----+-----+-----+-----+-----+-----+-----+ a | a,1 a,2 a,3 a,4 a,5 a,6 a,7 a,8 a,9 b | a,2 b,1 b,3 b,4 b,5 b,6 b,7 b,8 b,9 c | c,1 c,2 a,3 a,4 a,5 c,6 c,7 c,8 c,9 d | d,1 d,2 a,4 a,5 b,3 d,6 d,7 d,8 d,9 e | e,1 e,2 e,3 e,4 e,5 a,6 a,7 a,8 a,9 f | f,1 f,2 f,3 f,4 f,5 a,7 a,8 a,9 b,6 ---+-----+-----+-----+-----+-----+-----+-----+-----+-----+
‣ DirectProductOp( FR, machines, machine ) | ( method ) |
Returns: A new FR machine on the cartesian product of the arguments' alphabets.
The direct product of FR machines is defined as the FR machine with stateset generated by the product of the statesets, acting on the product of the alphabets; if these alphabets are [1..n1] up to [1..nk], then the alphabet of their product is [1..n1*...*nk] and the output and transition functions act component-wise.
The first argument is a list; the second argument is any element of that list, and is used only to improve the method selection algorithm.
gap> m := DirectProduct(AddingMachine(2),AddingMachine(3)); AddingMachine(2)xAddingMachine(3) gap> Display(last); | 1 2 3 4 5 6 ---+-----+-----+-----+-----+-----+-----+ a | a,1 a,2 a,3 a,4 a,5 a,6 b | a,2 a,3 b,1 a,5 a,6 b,4 c | a,4 a,5 a,6 c,1 c,2 c,3 d | a,5 a,6 b,4 c,2 c,3 d,1 ---+-----+-----+-----+-----+-----+-----+
‣ TreeWreathProduct( m, n, x0, y0 ) | ( method ) |
Returns: A new FR machine on the cartesian product of the arguments' alphabets.
The tree-wreath product of two FR machines is a machine acting on the product of its arguments' alphabets \(X,Y\), in such a way that many images of the first machine's states under conjugation by the second commute.
It is introduced (in lesser generality, and with small variations) in [Sid05], and may be described as follows: one takes two copies of the stateset of m, one copy of the stateset of n, and, if necessary, an extra identity state.
The first copy of m fixes the alphabet \(X\times Y\); its state \(\tilde s\) has transitions to the identity except \(\tilde s\) at \((x0,y0)\) and \(s\) at \((*,y0)\) for any other \(*\). The second copy of m is also trivial except that, on input \((x,y0)\), its state \(s\) goes to state \(s'\) with output \((x',y0)\) whenever \(s\) originally went, on input \(x\), to state \(s'\) with output \(x'\). This copy of m therefore acts only in the \(X\) direction, on the subtree \((X\times\{y0\})^\infty\), on subtrees below vertices of the form \((x0,y0)^t(x,y0)\).
A state \(t\) in the copy of n maps the input \((x,y)\) to \((x,y')\) and proceeds to state \(t'\) if \(y=y0\), and to the identity state otherwise, when on input \(y\) the original machine mapped state \(t\) to output \(t'\) and output \(y'\).
gap> m := TreeWreathProduct(AddingMachine(2),AddingMachine(3),1,1); AddingMachine(2)~AddingMachine(3) gap> Display(last); | 1 2 3 4 5 6 ---+-----+-----+-----+-----+-----+-----+ a | c,2 c,3 a,1 c,5 c,6 c,4 b | c,4 c,2 c,3 b,1 c,5 c,6 c | c,1 c,2 c,3 c,4 c,5 c,6 d | d,1 c,2 c,3 b,4 c,5 c,6 ---+-----+-----+-----+-----+-----+-----+
‣ SubFRMachine( machine1, machine2 ) | ( operation ) |
‣ SubFRMachine( machine1, f ) | ( operation ) |
Returns: Either fail or an embedding of the states of machine2 in the states of machine1.
In its first form, this function attempts to locate a copy of machine2 in machine1. If is succeeds, it returns a homomorphism from the stateset of machine2 into the stateset of machine1; otherwise it returns fail.
In its second form, this function attempts to construct a machine with stateset the source of f, that could be identified as a submachine of machine1 via f.
gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]); <FR machine with alphabet [ 1, 2 ] on Group( [ tau, mu ] )> gap> tauinv := FRMachine([[[1],[]]],[(1,2)]); <FR machine with alphabet [ 1, 2 ] on Group( [ f1 ] )> gap> SubFRMachine(n,tauinv); [ f1 ] -> [ tau^-1 ] gap> SubFRMachine(n,last); <FR machine with alphabet [ 1, 2 ] on Group( [ f1 ] )>
‣ ChangeFRMachineBasis( m[, l][, p] ) | ( attribute ) |
Returns: An equivalent FR machine, in a new basis.
This function constructs a new group FR machine, given a group FR machine m and, optionally, a list of states l (as elements of the free object StateSet(m)) and a permutation p, which defaults to the identity permutation.
The new machine has the following transitions: if alphabet letter a is mapped to b by state s in m, leading to state t, then, in the new machine, the input letter a^p is mapped to b^p by state s, leading to state l[a]^-1*t*l[b].
The group generated by the new machine is isomorphic to the group generated by m. This command amounts to a change of basis of the associated bimodule (see [Nek05, Section 2.2]). It amounts to conjugation by the automorphism c=FRElement("c",[l[1]*c,...,l[n]*c],[()],1).
If the second argument is absent, this command attempts to choose a list that makes many entries of the recursion trivial.
gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]);; gap> Display(n); G | 1 2 -----+--------+---------+ tau | <id>,2 tau,1 mu | <id>,2 mu^-1,1 -----+--------+---------+ gap> nt := ChangeFRMachineBasis(n,GeneratorsOfFRMachine(n){[1,1]});; gap> Display(nt); G | 1 2 -----+--------+--------------------+ tau | <id>,2 tau,1 mu | <id>,2 tau^-1*mu^-1*tau,1 -----+--------+--------------------+
‣ Minimized( m ) | ( operation ) |
Returns: A minimized machine equivalent to m.
This function attempts to construct a machine equivalent to m, but with a stateset of smaller rank. Identical generators are collapsed to a single generator of the stateset; if m is a group or monoid machine then trivial generators are removed; if m is a group machine then mutually inverse generators are grouped. This function sets as Correspondence(result) a mapping between the stateset of m and the stateset of the result; see Correspondence (3.5-12).
gap> n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]);; gap> m := FRMachine(["tauinv"],[[[1],[]]],[(1,2)]);; gap> sum := n+m+n; <FR machine with alphabet [ 1, 2 ] on Group( [ tau1, mu1, tauinv1, tau2, mu2 ] )> gap> min := Minimized(sum); <FR machine with alphabet [ 1, 2 ] on Group( [ tau1, mu1 ] )> gap> Correspondence(min); [ tau1, mu1, tauinv1, tau2, mu2 ] -> [ tau1, mu1, tau1^-1, tau1, mu1 ]
‣ Correspondence( m ) | ( attribute ) |
Returns: A mapping between statesets of FR machines.
If a machine m was created as a minimized group/monoid/semigroup machine, then Correspondence(m) is a mapping between the stateset of the original machine and the stateset of m. See Minimized (3.5-11) for an example.
If m was created as a minimized Mealy machine, then Correspondence(m) is a list identifying, for each state of the original machine, a state of the new machine. If the original state is inaccessible, the corresponding list entry is unbound. See Minimized (5.2-2) for an example.
If m was created using AsGroupFRMachine (3.3-4), AsMonoidFRMachine (3.3-4), AsSemigroupFRMachine (3.3-4), or AsMealyMachine (5.2-18), then Correspondence(m) is a list or a homomorphism identifying for each generator of the original machine a generator, or word in the generators, of the new machine. It is a list if either the original or the final machine is a Mealy machine, and a homomorphism in other cases.
If m was created as a sum of two machines, then m has a mapping Correspondence(m)[i] between the stateset of machine i=1,2 and its own stateset. See \+ (3.5-2) for an example.
generated by GAPDoc2HTML