A functionally recursive element is given by a functionally recursive machine and an initial state q. Many functions for FR machines, which accept a state as an argument, apply to FR elements. In that case, no state is passed to the function.
The main function of FR elements is to serve as group/monoid/semigroup elements: they can be multiplied and divided, and they act naturally on sequences. They can also be tested for equality, and can be sorted.
FR elements are stored as free group/monoid/semigroup words. They are printed as <n|w>, where n is the degree of their alphabet.
Equality of FR elements is tested as follows. Given FR elements (m,q) and (m,r), we set up a "rewriting system" for m, which records a purported set of relations among states of m. We start by an empty rewriting system, and we always ensure that the rewriting system is reduced and shortlex-reducing. Then, to compare q and r, we first compare their activities. If they differ, the elements are distinct. Otherwise, we reduce q and r using the rewriting system. If the resulting words are graphically equal, then they are equal. Otherwise, we add the rule q-> r or r-> q to the rewriting system, and proceed recursively to compare coordinatewise the states of these reduced words. As a bonus, we keep the rewriting system to speed up future comparisons.
Efficient comparison requires lookup in sorted lists, aka "Sets". Given two FR elements x and y, we declare that x<y if, for the shortlex-first sequence l such that Output(Transition(x,l)) and Output(Transition(y,l)) differ, the former is less than the latter (compared as lists). In fact, a single internal function compares x and y and returns -1,0,1 depending on whether x<y or x=y or x>y. It traverses, in breadth first fashion, the alphabet sequences, and stops either when provably x=y or if different outputs appear.
FRElements‣ FRElementNC( fam, free, transitions, outputs, init ) | ( operation ) |
Returns: A new FR element.
This function constructs a new FR element, belonging to family fam. It has stateset the free group/semigroup/monoid free, and transitions described by states and outputs, and initial states init.
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 a list of lists; outputs[s][x] is a output letter of the machine when it receives input x in state s.
init is a word in free.
gap> f := FreeGroup(2); <free group on the generators [ f1, f2 ]> gap> e := FRElementNC(FREFamily([1,2]),f,[[One(f),f.1],[One(f),f.2^-1]], [[2,1],[2,1]],f.1); <2|f1>
‣ FRElement( [names, ]transitions, outputs, init ) | ( operation ) |
‣ FRElement( free, transitions, outputs, init ) | ( operation ) |
Returns: A new FR element.
This function constructs a new FR element. It has stateset a free group/semigroup/monoid, structure described by transitions and outputs, and initial state init. If the stateset is not passed as argument free, then it is determined by transitions and outputs; it is a free group if all states are invertible, and a free monoid otherwise. In that case, names is an optional list; at position s it contains a string describing generator s.
transitions is a list of lists; transitions[s][x] is either an associative word, or a list of integers or FR elements describing the state reached by the machine when started in state s and fed input x. Positive integers indicate a generator, 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 element.
outputs is a list; at position s it contains a permutation, a transformation, or a list of images, describing the activity of state s.
init is either an associative word, an integer, or a list of integers describing the inital state of the machine.
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]); <2|tau> gap> tau1 := FRElement(["tau1","tau"],[[[],[2]],[[],[2]]],[(),(1,2)],1); <2|tau1> gap> (tau/tau1)^2; <2|tau1*tau2^-1*tau1*tau2^-1> gap> IsOne(last); true
gap> f := FreeGroup("tau","tau1"); <free group on the generators [ tau, tau1 ]> gap> tau := FRElement(f,[[One(f),f.1],[One(f),f.1]],[(1,2),()],f.1); <2|tau> gap> tau1 := FRElement(f,[[One(f),f.1],[One(f),f.1]],[(1,2),()],f.2); <2|tau1> gap> (tau/tau1)^2; <2|tau1*tau2^-1*tau1*tau2^-1> gap> IsOne(last); true gap> tauX := FRElement(f,[[One(f),f.1],[One(f),f.1]],[(1,2),()],1);; gap> tauY := FRElement(f,[[One(f),f.1],[One(f),f.1]],[(1,2),()],f.1);; gap> Size(Set([tau,tauX,tauY])); 1
‣ FRElement( m, q ) | ( operation ) |
Returns: A new FR element.
This function constructs a new FR element. If m is an FR machine, it creates the element (m,q) whose FRMachine is m and whose initial state is q.
If m is an FR element, this command creates an FR element with the same FR machine as m, and with initial state q.
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> Comm(b,b^a); <2|b^-1*a^-1*b^-1*a*b*a^-1*b*a> gap> IsOne(last); true gap> last2=FRElement(m,[-2,-1,-2,1,2,-1,2,1]); true
‣ ComposeElement( l, p ) | ( operation ) |
Returns: A new FR element.
This function constructs a new FR element. l is a list of FR elements, and p is a permutation, transformation or list. In that last case, the resulting element g satisfies DecompositionOfFRElement(g)=[l,p].
If all arguments are Mealy elements, the result is a Mealy element. Otherwise, it is a MonoidFRElement.
gap> m := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]);; gap> a := FRElement(m,1); b := FRElement(m,2); <2|a> <2|b> gap> ComposeElement([b^0,b],(1,2)); <2|f1> gap> last=a; true gap> DecompositionOfFRElement(last2); [ [ <2|identity ...>, <2|f5> ], [ 2, 1 ] ]
‣ VertexElement( v, e ) | ( operation ) |
Returns: A new FR element.
This function constructs a new FR element. v is either an integer or a list of integers, and represents a vertex. e is an FR element. The resulting element acts on the subtree below vertex v as e acts on the whole tree, and fixes all other subtrees.
gap> e := FRElement([[[],[]]],[(1,2)],[1]); <2|f1> gap> f := VertexElement(1,e);; gap> g := VertexElement(2,f);; gap> g = VertexElement([2,1],e); true gap> 1^e; 2 gap> [1,1]^f; [ 1, 2 ] gap> [2,1,1]^g; [ 2, 1, 2 ]
‣ DiagonalElement( n, e ) | ( operation ) |
Returns: A new FR element.
This function constructs a new FR element. n is either an integer or a list of integers, representing a sequence of operations to be performed on e starting from the last.
DiagonalElement(n,e) is an element with trivial output, and with e^(-1)^i binomial(n,i) in coordinate i+1 of the alphabet, assumed to be of the form [1..d].
In particular, DiagonalElement(0,e) is the same as VertexElement(1,e); DiagonalElement(1,e) is the commutator of VertexElement(1,e) with any cycle mapping 1 to 2; and DiagonalElement(-1,e) has a transition to e at all inputs.
gap> e := FRElement([[[],[],[1]]],[(1,2,3)],[1]); <3|f1> gap> Display(e); | 1 2 3 ----+--------+--------+------+ f1 | <id>,2 <id>,3 f1,1 ----+--------+--------+------+ Initial state: f1 gap> Display(DiagonalElement(0,e)); | 1 2 3 ----+--------+--------+--------+ f1 | f2,1 <id>,2 <id>,3 f2 | <id>,2 <id>,3 f2,1 ----+--------+--------+--------+ Initial state: f1 gap> Display(DiagonalElement(1,e)); | 1 2 3 ----+--------+---------+--------+ f1 | f2,1 f2^-1,2 <id>,3 f2 | <id>,2 <id>,3 f2,1 ----+--------+---------+--------+ Initial state: f1 gap> Display(DiagonalElement(2,e)); | 1 2 3 ----+--------+---------+------+ f1 | f2,1 f2^-2,2 f2,3 f2 | <id>,2 <id>,3 f2,1 ----+--------+---------+------+ Initial state: f1 gap> Display(DiagonalElement(-1,e)); | 1 2 3 ----+--------+--------+------+ f1 | f2,1 f2,2 f2,3 f2 | <id>,2 <id>,3 f2,1 ----+--------+--------+------+ Initial state: f1 gap> DiagonalElement(-1,e)=DiagonalElement(2,e); true gap> Display(DiagonalElement([0,-1],e)); G | 1 2 3 ----+--------+--------+--------+ f1 | f2,1 <id>,2 <id>,3 f2 | f3,1 f3,2 f3,3 f3 | <id>,2 <id>,3 f3,1 ----+--------+--------+--------+ Initial state: f1 gap> Display(DiagonalElement([-1,0],e)); G | 1 2 3 ----+--------+--------+--------+ f1 | f2,1 f2,2 f2,3 f2 | f3,1 <id>,2 <id>,3 f3 | <id>,2 <id>,3 f3,1 ----+--------+--------+--------+ Initial state: f1
‣ AsGroupFRElement( e ) | ( operation ) |
‣ AsMonoidFRElement( e ) | ( operation ) |
‣ AsSemigroupFRElement( e ) | ( operation ) |
Returns: An FR element isomorphic to m, with a free group/monoid/semigroup as stateset.
This function constructs, from the FR element e, an isomorphic FR element f with a free group/monoid/semigroup as stateset. e may be a Mealy, group, monoid or semigroup FR element.
gap> e := AsGroupFRElement(FRElement(GuptaSidkiMachines(3),4)); <3|f1> gap> Display(e); G | 1 2 3 ----+--------+---------+--------+ f1 | f2,1 f2^-1,2 f1,3 f2 | <id>,2 <id>,3 <id>,1 ----+--------+---------+--------+ Initial state: f1 gap> e=FRElement(GuptaSidkiMachines(3),4); #I \=: converting second argument to FR element true
gap> e := AsMonoidFRElement(FRElement(GuptaSidkiMachines(3),4)); <3|m1> gap> Display(e); M | 1 2 3 ----+--------+--------+--------+ m1 | m2,1 m3,2 m1,3 m2 | <id>,2 <id>,3 <id>,1 m3 | <id>,3 <id>,1 <id>,2 ----+--------+--------+--------+ Initial state: m1 gap> e=FRElement(GuptaSidkiMachines(3),4); #I \=: converting second argument to FR element true
gap> e := AsSemigroupFRElement(FRElement(GuptaSidkiMachines(3),4)); <3|s1> gap> Display(e); S | 1 2 3 ----+------+------+------+ s1 | s2,1 s3,2 s1,3 s2 | s4,2 s4,3 s4,1 s3 | s4,3 s4,1 s4,2 s4 | s4,1 s4,2 s4,3 ----+------+------+------+ Initial state: s1 gap> e=FRElement(GuptaSidkiMachines(3),4); #I \=: converting second argument to FR element true
FRElements‣ Output( e ) | ( operation ) |
Returns: A transformation of e's alphabet.
This function returns the transformation of e's alphabet, i.e. the action on strings of length 1 over the alphabet. This transformation is a permutation if machine is a group machine, and a transformation otherwise.
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);; gap> Output(tau); (1,2) zap := FRElement(["zap"],[[[],[1]]],[[1,1]],[1]);; gap> Output(zap); <1,1>
‣ Activity( e[, l] ) | ( operation ) |
‣ ActivityInt( e[, l] ) | ( operation ) |
‣ ActivityTransformation( e[, l] ) | ( operation ) |
‣ ActivityPerm( e[, l] ) | ( operation ) |
Returns: The transformation induced by e on the lth level of the tree.
This function returns the transformation induced by e on the lth level of the tree, i.e. on the strings of length l over e's alphabet.
This set of strings is identified with the set L={1,...,d^l} of integers, where the alphabet of e has d letters. Changes of the first letter of a string induce changes of a multiple of d^l-1 on the position in L, while changes of the last letter of a string induce changes of 1 on the position in L.
In its first form, this command returns a permutation (for group elements) or a Transformation (Reference: Transformation for an image list) (for other elements). In the second form, it returns the unique integer i such that the transformation e acts on [1..Length(AlphabetOfFRObject(e))^n] as adding i in base Length(alphabet(e)), or fail if no such i exists. In the third form, it returns a GAP transformation. In the fourth form, it returns a permutation, or fail if e is not invertible.
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);; gap> Output(tau); PermList(last)=Activity(tau); [ 2, 1 ] true gap> Activity(tau,2); ActivityInt(tau,2); (1,3,2,4) 1 gap> Activity(tau,3); ActivityInt(tau,3); (1,5,3,7,2,6,4,8) 1 gap> zap := FRElement(["zap"],[[[1],[]]],[[1,1]],[1]); <2|zap> gap> Output(zap); [ 1, 1 ] gap> Activity(zap,3); <1,1,1,2,1,2,3,4>
‣ Transition( e, i ) | ( operation ) |
Returns: An element of machine's stateset.
This function returns the state reached by e when fed input i. This input may be an alphabet letter or a sequence of alphabet letters.
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);; gap> Transition(tau,2); tau gap> Transition(tau,[2,2]); tau gap> Transition(tau^2,[2,2]); tau
‣ Transitions( e ) | ( operation ) |
Returns: A list of elements of machine's stateset.
This function returns the states reached by e when fed the alphabet as input.
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);; gap> Transitions(tau); [ <identity ...>, tau ] gap> Transition(tau^2); [ tau, tau ]
‣ Portrait( e, l ) | ( operation ) |
‣ PortraitPerm( e, l ) | ( operation ) |
‣ PortraitTransformation( e, l ) | ( operation ) |
‣ PortraitInt( e, l ) | ( operation ) |
Returns: A nested list describing the action of e.
This function returns a sequence of l+1 lists; the ith list in the sequence is an i-1-fold nested list. The entry at position (x_1,...,x_i) is the transformation of the alphabet induced by e under vertex x_1... x_i.
The difference between the commands is the following: Portrait returns transformations, PortraitPerm returns permutations, and and PortraitInt returns integers, the power of the cycle x↦ x+1 that represents the transformation, as for the function ActivityInt (4.2-2).
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);; gap> Portrait(tau,0); [ <2,1> ] gap> Portrait(tau,3); [ <2,1>, [ <>, <2,1> ], [ [ <>, <> ], [ <>, <2,1> ] ], [ [ [ <>, <> ], [ <>, <> ] ], [ [ <>, <> ], [ <>, <2,1> ] ] ] ] gap> PortraitPerm(tau,0); [ (1,2) ] gap> PortraitInt(tau,0); [ 1 ] gap> PortraitInt(tau,3); [ 1 , [ 0 , 1 ], [ [ 0 , 0 ], [ 0 , 1 ] ], [ [ [ 0 , 0 ], [ 0 , 0 ] ], [ [ 0 , 0 ], [ 0 , 1 ] ] ] ]
‣ DecompositionOfFRElement( e[, n] ) | ( operation ) |
Returns: A list describing the action and transitions of e.
This function returns a list. The second coordinate is the action of e on its alphabet, see Output (4.2-1). The first coordinate is a list, containing in position i the FR element inducing the action of e on strings starting with i.
If a second argument n is supplied, the decomposition is iterated n times.
This FR element has same underlying machine as e, and initial state given by Transition (4.2-3).
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);; gap> DecompositionOfFRElement(tau); [ [ <2|identity ...>, <2|tau> ], [ 2, 1 ] ]
‣ StateSet( e ) | ( operation ) |
Returns: The set of states associated with e.
This function returns the stateset of e. If e is of Mealy type, this is the list of all states reached by e.
If e is of group/semigroup/monoid type, then this is the stateset of the underlying FR machine, and not the minimal set of states of e, which is computed with States (4.2-9).
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);; gap> StateSet(tau); <free group on the generators [ tau ]>
‣ State( e, v ) | ( operation ) |
Returns: An FR element describing the action of e at vertex v.
This function returns the FR element with same underlying machine as e, acting on the binary tree as e acts on the subtree below v.
v is either an integer or a list. This function returns an FR element, but otherwise is essentially a call to Transition (4.2-3).
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);; gap> State(tau,2); <2|tau> gap> State(tau,[2,2]); <2|tau> gap> State(tau^2,[2,2]); <2|tau>
‣ States( e ) | ( operation ) |
Returns: A list of FR elements describing the action of e on all subtrees.
This function calls repeatedly State (4.2-8) to compute all the states of e; it returns the smallest list of FRElements that is closed under the function State (4.2-8).
e may be either an FR element, or a list of FR elements. In the latter case, it amounts to computing the list of all states of all elements of the list e.
The ordering of the list is as follows. First come e, or all elements of e. Then come the states reached by e in one transition, ordered by the alphabet letter leading to them; then come those reached in two transitions, ordered lexicographically by the transition; etc.
Note that this function is not guaranteed to terminate. There is currently no mechanism that detects whether an FR element is finite state, so in fact this function terminates if and only if e is finite-state.
gap> m := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]);; gap> a := FRElement(m,1);; b := FRElement(m,2);; gap> States(a); [ <2|a>, <2|identity ...>, <2|b> ] gap> States(b); [ <2|b>, <2|identity ...>, <2|a> ] gap> States(a^2); [ <2|a^2>, <2|b>, <2|identity ...>, <2|a> ]
‣ FixedStates( e ) | ( operation ) |
Returns: A list of FR elements describing the action of e at fixed vertices.
This function calls repeatedly State (4.2-8) to compute all the states of e at non-trivial fixed vertices.
e may be either an FR element, or a list of FR elements. In the latter case, it amounts to computing the list of all states of all elements of the list e.
The ordering of the list is as follows. First come e, or all elements of e. Then come the states reached by e in one transition, ordered by the alphabet letter leading to them; then come those reached in two transitions, ordered lexicographically by the transition; etc.
Note that this function is not guaranteed to terminate, if e is not finite-state.
gap> m := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]);; gap> a := FRElement(m,1);; b := FRElement(m,2);; gap> FixedStates(a); [ ] gap> FixedStates(b); [ <2|identity ...>, <2|a> ] gap> FixedStates(a^2); [ <2|b>, <2|identity ...>, <2|a> ]
‣ LimitStates( e ) | ( operation ) |
Returns: A set of FR element describing the recurring actions of e on all subtrees.
This function computes the States (4.2-9) S of e, and then repeatedly removes elements that are not recurrent, i.e. that do not appear as states of elements of S on subtrees distinct from the entire tree; and then converts the result to a set.
As for States (4.2-9), e may be either an FR element, or a list of FR elements.
Note that this function is not guaranteed to terminate. It currently terminates if and only if States (4.2-9) terminates.
gap> m := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]);; gap> a := FRElement(m,1);; b := FRElement(m,2);; gap> LimitStates(a); [ <2|identity ...>, <2|b>, <2|a> ] gap> LimitStates(a^2); [ <2|identity ...>, <2|b>, <2|a> ]
‣ IsFiniteStateFRElement( e ) | ( property ) |
‣ IsFiniteStateFRMachine( e ) | ( property ) |
Returns: true if e is a finite-state element.
This function tests whether e is a finite-state element.
When applied to a Mealy element, it returns true.
gap> m := GuptaSidkiMachines(3);; Display(m); | 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> Filtered(StateSet(m),i->IsFiniteStateFRElement(FRElement(m,i))); [ 1, 2, 3, 4 ] gap> IsFiniteStateFRMachine(m); true
‣ NucleusOfFRMachine( m ) | ( operation ) |
‣ Nucleus( m ) | ( operation ) |
Returns: The nucleus of the machine m.
This function computes the nucleus of the machine m. It is the minimal set N of states such that, for every word s in the states of m, all states of s of at large enough depth belong to .
It may also be characterized as the minimal set N of states that contains the limit states of m and is such that the limit states of N*m belong to N.
The elements of the nucleus form the stateset of a Mealy machine; this machine is created by NucleusMachine (5.2-27).
This command is not guaranteed to terminate; though it will, if the semigroup generated by m is contracting. If the minimal such N is infinite, this command either returns K or runs forever.
gap> m := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]);; gap> NucleusOfFRMachine(m); [ <2|identity ...>, <2|b>, <2|a> ] gap> m := FRMachine(["a","b"],[[[],[1]],[[1],[2]]],[(1,2),()]);; gap> NucleusOfFRMachine(m); fail
‣ InitialState( e ) | ( operation ) |
Returns: The initial state of an FR element.
This function returns the initial state of an FR element. It is an element of the stateset of the underlying FR machine of e.
gap> n := FRElement(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)],[1,2]); <2|tau*mu> gap> InitialState(n); tau*mu gap> last in StateSet(n); true
4.2-15 \^‣ \^( e, v ) | ( method ) |
Returns: The image of a vertex v under e.
This function accepts an FR element and a vertex v, which is either an integer or a list. It returns the image of v under the transformation e, in the same format (integer/list) as v.
The list v can be a periodic list (see PeriodicList (11.2-2)). In that case, the result is again a periodic list. The computation will succeed only if the states along the period are again periodic.
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);; gap> 1^tau; 2 gap> [1,1]^tau; [ 2, 1 ] gap> [2,2,2]^tau; [ 1, 1, 1 ] gap List([0..5],i->PeriodicList([],[2])^(tau^i)); [ [/ 2 ], [/ 1 ], [ 2, / 1 ], [ 1, 2, / 1 ], [ 2, 2, / 1 ], [ 1, 1, 2, / 1 ] ]
4.2-16 \*‣ \*( m, n ) | ( method ) |
Returns: The product of the two FR elements m and n.
This function returns a new FR element, which is the product of the FR elements m and n.
In case m and n have the same underlying machine, this is the machine of the result. In case the machine of n embeds in the machine of m (see SubFRMachine (3.5-9)), the machine of the product is the machine of m. In case the machine of m embeds in the machine of n, the machine of the product is the machine of n. Otherwise the machine of the product is the product of the machines of m and n (See \* (3.5-3)).
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);; gap> tau*tau; tau^2; <2|tau^2> <2|tau^2> gap> [2,2,2]^(tau^2); [ 2, 1, 1 ]
4.2-17 \[\]‣ \[\]( m, i ) | ( method ) |
‣ \{\}( m, l ) | ( method ) |
Returns: A [list of] FR element[s] with initial state i.
These are respectively synonyms for FRElement(m,i) and List(l,s->FRElement(m,s)). The argument m must be an FR machine, i must be a positive integer, and l must be a list.
generated by GAPDoc2HTML