<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>GAP (FR) - Chapter 4: Functionally recursive elements</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8" />
<meta name="generator" content="GAPDoc2HTML" />
<link rel="stylesheet" type="text/css" href="manual.css" />
</head>
<body>
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0.html">Top of Book</a> <a href="chap3.html">Previous Chapter</a> <a href="chap5.html">Next Chapter</a> </div>
<p><a id="X863D82207A1320F1" name="X863D82207A1320F1"></a></p>
<div class="ChapSects"><a href="chap4.html#X863D82207A1320F1">4 <span class="Heading">Functionally recursive elements</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap4.html#X79DE08CD7EE57360">4.1 <span class="Heading">Creators for <code class="code">FRElement</code>s</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7839813183881054">4.1-1 FRElementNC</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7CF5EDEB874BF9E3">4.1-2 FRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X86181654827919EE">4.1-3 FRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X80D518E2804ABF70">4.1-4 ComposeElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7CE388057DAB4802">4.1-5 VertexElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X848EB430831097E6">4.1-6 DiagonalElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7EB5DE3978840CDF">4.1-7 AsGroupFRElement</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap4.html#X812C932C7E2F2885">4.2 <span class="Heading">Operations and Attributes for <code class="code">FRElement</code>s</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X78F819CF7DDBF310">4.2-1 Output</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8732D01C82999F32">4.2-2 Activity</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7CE58B2D837B2845">4.2-3 Transition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X84A193C67CDBDA35">4.2-4 Portrait</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X850EB66E7804BA3B">4.2-5 DecompositionOfFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X85441F1683E9D820">4.2-6 StateSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X819E3E3080297347">4.2-7 State</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7B0C97BC7C3BA20D">4.2-8 States</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X804B2E0F7E37F5B8">4.2-9 FixedStates</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X8303B36C83371FB3">4.2-10 LimitStates</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7C4076707CBBE945">4.2-11 IsFiniteStateFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X79E65E818690B4EB">4.2-12 InitialState</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X823B6E3D819432D6">4.2-13 \^</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X7C3CF6AF86336EDC">4.2-14 \*</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap4.html#X78C19ACA78F9F067">4.2-15 \[\]</a></span>
</div>
</div>
<h3>4 <span class="Heading">Functionally recursive elements</span></h3>
<p>A <em>functionally recursive element</em> 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.</p>
<p>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.</p>
<p>FR elements are stored as free group/monoid/semigroup words. They are printed as <code class="code"><n|w></code>, where <code class="code">n</code> is the degree of their alphabet.</p>
<p>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.</p>
<p>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 <code class="code">Output(Transition(x,l))</code> and <code class="code">Output(Transition(y,l))</code> 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.</p>
<p><a id="X79DE08CD7EE57360" name="X79DE08CD7EE57360"></a></p>
<h4>4.1 <span class="Heading">Creators for <code class="code">FRElement</code>s</span></h4>
<p><a id="X7839813183881054" name="X7839813183881054"></a></p>
<h5>4.1-1 FRElementNC</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FRElementNC</code>( <var class="Arg">fam, free, transitions, outputs, init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new FR element.</p>
<p>This function constructs a new FR element, belonging to family <var class="Arg">fam</var>. It has stateset the free group/semigroup/monoid <var class="Arg">free</var>, and transitions described by <var class="Arg">states</var> and <var class="Arg">outputs</var>, and initial states <var class="Arg">init</var>.</p>
<p><var class="Arg">transitions</var> is a list of lists; <var class="Arg">transitions</var>[<var class="Arg">s</var>][<var class="Arg">x</var>] is a word in <var class="Arg">free</var>, which is the state reached by the machine when started in state <var class="Arg">s</var> and fed input <var class="Arg">x</var>.</p>
<p><var class="Arg">outputs</var> is a list of lists; <var class="Arg">outputs</var>[<var class="Arg">s</var>][<var class="Arg">x</var>] is a output letter of the machine when it receives input <var class="Arg">x</var> in state <var class="Arg">s</var>.</p>
<p><var class="Arg">init</var> is a word in <var class="Arg">free</var>.</p>
<table class="example">
<tr><td><pre>
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>
</pre></td></tr></table>
<p><a id="X7CF5EDEB874BF9E3" name="X7CF5EDEB874BF9E3"></a></p>
<h5>4.1-2 FRElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FRElement</code>( <var class="Arg">[names, ]transitions, outputs, init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FRElement</code>( <var class="Arg">free, transitions, outputs, init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new FR element.</p>
<p>This function constructs a new FR element. It has stateset a free group/semigroup/monoid, structure described by <var class="Arg">transitions</var> and <var class="Arg">outputs</var>, and initial state <var class="Arg">init</var>. If the stateset is not passed as argument <var class="Arg">free</var>, then it is determined by <var class="Arg">transitions</var> and <var class="Arg">outputs</var>; it is a free group if all states are invertible, and a free monoid otherwise. In that case, <var class="Arg">names</var> is an optional list; at position <var class="Arg">s</var> it contains a string naming generator <var class="Arg">s</var>.</p>
<p><var class="Arg">transitions</var> is a list of lists; <code class="code">transitions[s][x]</code> is either an associative word, or a list of integers or FR elements describing the state reached by the machine when started in state <var class="Arg">s</var> and fed input <var class="Arg">x</var>. 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.</p>
<p><var class="Arg">outputs</var> is a list; at position <var class="Arg">s</var> it contains a permutation, a transformation, or a list of images, describing the activity of state <var class="Arg">s</var>.</p>
<p><var class="Arg">init</var> is either an associative word, an integer, or a list of integers describing the inital state of the machine.</p>
<table class="example">
<tr><td><pre>
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);
<2|tau>
gap> tau1 := FRElement(["tau1"],[[[],[2]],[[],[2]]],[(),(1,2)],1);
<2|tau1>
gap> (tau/tau1)^2;
<2|tau1*tau2^-1*tau1*tau2^-1>
gap> IsOne(last);
true
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
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
</pre></td></tr></table>
<p><a id="X86181654827919EE" name="X86181654827919EE"></a></p>
<h5>4.1-3 FRElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FRElement</code>( <var class="Arg">m, q</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new FR element.</p>
<p>This function constructs a new FR element. If <var class="Arg">m</var> is an FR machine, it creates the element (m,q) whose <code class="code">FRMachine</code> is <var class="Arg">m</var> and whose initial state is <var class="Arg">q</var>.</p>
<p>If <var class="Arg">m</var> is an FR element, this command creates an FR element with the same FR machine as <var class="Arg">m</var>, and with initial state <var class="Arg">q</var>.</p>
<table class="example">
<tr><td><pre>
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
</pre></td></tr></table>
<p><a id="X80D518E2804ABF70" name="X80D518E2804ABF70"></a></p>
<h5>4.1-4 ComposeElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ComposeElement</code>( <var class="Arg">l, p</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new FR element.</p>
<p>This function constructs a new FR element. <var class="Arg">l</var> is a list of FR elements, and <var class="Arg">p</var> is a permutation, transformation or list. In that last case, the resulting element <code class="code">g</code> satisfies <code class="code">DecompositionOfFRElement(g)=[l,p]</code>.</p>
<p>If all arguments are Mealy element, the result is a Mealy element. Otherwise, it is a MonoidFRElement.</p>
<table class="example">
<tr><td><pre>
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 ] ]
</pre></td></tr></table>
<p><a id="X7CE388057DAB4802" name="X7CE388057DAB4802"></a></p>
<h5>4.1-5 VertexElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VertexElement</code>( <var class="Arg">v, e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new FR element.</p>
<p>This function constructs a new FR element. <var class="Arg">v</var> is either an integer or a list of integers, and represents a vertex. <var class="Arg">e</var> is an FR element. The resulting element acts on the subtree below vertex <var class="Arg">v</var> as <var class="Arg">e</var> acts on the whole tree, and fixes all other subtrees.</p>
<table class="example">
<tr><td><pre>
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 ]
</pre></td></tr></table>
<p><a id="X848EB430831097E6" name="X848EB430831097E6"></a></p>
<h5>4.1-6 DiagonalElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DiagonalElement</code>( <var class="Arg">n, e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new FR element.</p>
<p>This function constructs a new FR element. <var class="Arg">n</var> is either an integer or a list of integers, representing a sequence of operations to be performed on <var class="Arg">e</var> starting from the last.</p>
<p><code class="code">DiagonalElement(n,e)</code> 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 <code class="code">[1..d]</code>.</p>
<p>In particular, <code class="code">DiagonalElement(0,e)</code> is the same as <code class="code">VertexElement(1,e)</code>; <code class="code">DiagonalElement(1,e)</code> is the commutator of <code class="code">VertexElement(1,e)</code> with any cycle mapping 1 to 2; and <code class="code">DiagonalElement(-1,e)</code> has a transition to <var class="Arg">e</var> at all inputs.</p>
<table class="example">
<tr><td><pre>
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
</pre></td></tr></table>
<p><a id="X7EB5DE3978840CDF" name="X7EB5DE3978840CDF"></a></p>
<h5>4.1-7 AsGroupFRElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsGroupFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsMonoidFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsSemigroupFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An FR element isomorphic to <var class="Arg">m</var>, with a free group/monoid/semigroup as stateset.</p>
<p>This function constructs, from the FR element <var class="Arg">e</var>, an isomorphic FR element <code class="code">f</code> with a free group/monoid/semigroup as stateset. <var class="Arg">e</var> may be a Mealy, group, monoid or semigroup FR element.</p>
<table class="example">
<tr><td><pre>
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
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
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
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
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
</pre></td></tr></table>
<p><a id="X812C932C7E2F2885" name="X812C932C7E2F2885"></a></p>
<h4>4.2 <span class="Heading">Operations and Attributes for <code class="code">FRElement</code>s</span></h4>
<p><a id="X78F819CF7DDBF310" name="X78F819CF7DDBF310"></a></p>
<h5>4.2-1 Output</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Output</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A transformation of <var class="Arg">e</var>'s alphabet.</p>
<p>This function returns the transformation of <var class="Arg">e</var>'s alphabet, i.e. the action on strings of length 1 over the alphabet. This transformation is a permutation if <var class="Arg">machine</var> is a group machine, and a transformation otherwise.</p>
<table class="example">
<tr><td><pre>
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>
</pre></td></tr></table>
<p><a id="X8732D01C82999F32" name="X8732D01C82999F32"></a></p>
<h5>4.2-2 Activity</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Activity</code>( <var class="Arg">e[, l]</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ActivityInt</code>( <var class="Arg">e[, l]</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ActivityTransformation</code>( <var class="Arg">e[, l]</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ActivityPerm</code>( <var class="Arg">e[, l]</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The transformation induced by <var class="Arg">e</var> on the <var class="Arg">l</var>th level of the tree.</p>
<p>This function returns the transformation induced by <var class="Arg">e</var> on the <var class="Arg">l</var>th level of the tree, i.e. on the strings of length <var class="Arg">l</var> over <var class="Arg">e</var>'s alphabet.</p>
<p>This set of strings is identified with the set L={1,dots,d^l} of integers, where the alphabet of <var class="Arg">e</var> 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.</p>
<p>This command returns a permutation if <var class="Arg">e</var> is invertible; and a transformations otherwise. In the second form, it returns the unique integer <code class="code">i</code> such that the transformation <var class="Arg">e</var> acts on <code class="code">[1..Length(AlphabetOfFRObject(e))^n]</code> as adding <code class="code">i</code> in base <code class="code">Length(alphabet(e))</code>, or <code class="keyw">fail</code> if no such <code class="code">i</code> exists.</p>
<table class="example">
<tr><td><pre>
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
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>
</pre></td></tr></table>
<p><a id="X7CE58B2D837B2845" name="X7CE58B2D837B2845"></a></p>
<h5>4.2-3 Transition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Transition</code>( <var class="Arg">e, i</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An element of <var class="Arg">machine</var>'s stateset.</p>
<p>This function returns the state reached by <var class="Arg">e</var> when fed input <var class="Arg">i</var>. This input may be an alphabet letter or a sequence of alphabet letters.</p>
<table class="example">
<tr><td><pre>
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
</pre></td></tr></table>
<p><a id="X84A193C67CDBDA35" name="X84A193C67CDBDA35"></a></p>
<h5>4.2-4 Portrait</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Portrait</code>( <var class="Arg">e, l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> PortraitInt</code>( <var class="Arg">e, l</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A nested list describing the action of <var class="Arg">e</var>.</p>
<p>This function returns a sequence of l+1 lists; the ith list in the sequence is an <var class="Arg">i-1</var>-fold nested list. The entry at position (x_1,dots,x_i) is the transformation of the alphabet induced by <var class="Arg">e</var> under vertex x_1dots x_i.</p>
<p>The difference between <code class="code">Portrait</code> and <code class="code">Portrait</code> is that the latter describes transformations are described as powers of the cycle x-> x+1, as for the function <code class="func">ActivityInt</code> (<a href="chap4.html#X8732D01C82999F32"><b>4.2-2</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);;
gap> Portrait(tau,0);
[ (1,2) ]
gap> Portrait(tau,3);
[ (1,2), [ (), (1,2) ], [ [ (), () ], [ (), (1,2) ] ],
[ [ [ (), () ], [ (), () ] ], [ [ (), () ], [ (), (1,2) ] ] ] ]
gap> PortraitInt(tau,0);
[ ZmodpZObj(1,2) ]
gap> PortraitInt(tau,3);
[ ZmodpZObj(1,2), [ZmodpZObj(0,2), ZmodpZObj(1,2)],
[ [ZmodpZObj(0,2), ZmodpZObj(0,2)], [ZmodpZObj(0,2), ZmodpZObj(1,2)] ],
[ [ [ZmodpZObj(0,2), ZmodpZObj(0,2)], [ZmodpZObj(0,2), ZmodpZObj(0,2)] ],
[ [ZmodpZObj(0,2), ZmodpZObj(0,2)], [ZmodpZObj(0,2), ZmodpZObj(1,2)] ] ] ]
</pre></td></tr></table>
<p><a id="X850EB66E7804BA3B" name="X850EB66E7804BA3B"></a></p>
<h5>4.2-5 DecompositionOfFRElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DecompositionOfFRElement</code>( <var class="Arg">e[, n]</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A list describing the action and transitions of <var class="Arg">e</var>.</p>
<p>This function returns a list. The second coordinate is the action of <var class="Arg">e</var> on its alphabet, see <code class="func">Output</code> (<a href="chap4.html#X78F819CF7DDBF310"><b>4.2-1</b></a>). The first coordinate is a list, containing in position i the FR element inducing the action of <var class="Arg">e</var> on strings starting with i.</p>
<p>If a second argument <var class="Arg">n</var> is supplied, the decomposition is iterated <var class="Arg">n</var> times.</p>
<p>This FR element has same underlying machine as <var class="Arg">e</var>, and initial state given by <code class="func">Transition</code> (<a href="chap4.html#X7CE58B2D837B2845"><b>4.2-3</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);;
gap> DecompositionOfFRElement(tau);
[ [ <2|identity ...>, <2|tau> ], [ 2, 1 ] ]
</pre></td></tr></table>
<p><a id="X85441F1683E9D820" name="X85441F1683E9D820"></a></p>
<h5>4.2-6 StateSet</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> StateSet</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The set of states associated with <var class="Arg">e</var>.</p>
<p>This function returns the stateset of <var class="Arg">e</var>. If <var class="Arg">e</var> is of Mealy type, this is the list of all states reached by <var class="Arg">e</var>.</p>
<p>If <var class="Arg">e</var> is of group/semigroup/monoid type, then this is the stateset of the underlying FR machine, and not the minimal set of states of <var class="Arg">e</var>, which is computed with <code class="func">States</code> (<a href="chap4.html#X7B0C97BC7C3BA20D"><b>4.2-8</b></a>).</p>
<table class="example">
<tr><td><pre>
gap> tau := FRElement(["tau"],[[[],[1]]],[(1,2)],[1]);;
gap> StateSet(tau);
<free group on the generators [ tau ]>
</pre></td></tr></table>
<p><a id="X819E3E3080297347" name="X819E3E3080297347"></a></p>
<h5>4.2-7 State</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> State</code>( <var class="Arg">e, v</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An FR element describing the action of <var class="Arg">e</var> at vertex <var class="Arg">v</var>.</p>
<p>This function returns the FR element with same underlying machine as <var class="Arg">e</var>, acting on the binary tree as <var class="Arg">e</var> acts on the subtree below <var class="Arg">v</var>.</p>
<p><var class="Arg">v</var> is either an integer or a list. This function returns an FR element, but otherwise is essentially a call to <code class="func">Transition</code> (<a href="chap4.html#X7CE58B2D837B2845"><b>4.2-3</b></a>).</p>
<table class="example">
<tr><td><pre>
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>
</pre></td></tr></table>
<p><a id="X7B0C97BC7C3BA20D" name="X7B0C97BC7C3BA20D"></a></p>
<h5>4.2-8 States</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> States</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A list of FR elements describing the action of <var class="Arg">e</var> on all subtrees.</p>
<p>This function calls repeatedly <code class="func">State</code> (<a href="chap4.html#X819E3E3080297347"><b>4.2-7</b></a>) to compute all the states of <var class="Arg">e</var>; it returns the smallest list of <code class="code">FRElement</code>s that is closed under the function <code class="func">State</code> (<a href="chap4.html#X819E3E3080297347"><b>4.2-7</b></a>).</p>
<p><var class="Arg">e</var> 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 <var class="Arg">e</var>.</p>
<p>The ordering of the list is as follows. First come <var class="Arg">e</var>, or all elements of <var class="Arg">e</var>. Then come the states reached by <var class="Arg">e</var> in one transition, ordered by the alphabet letter leading to them; then come those reached in two transitions, ordered lexicographically by the transition; etc.</p>
<p>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 <var class="Arg">e</var> is finite-state.</p>
<table class="example">
<tr><td><pre>
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> ]
</pre></td></tr></table>
<p><a id="X804B2E0F7E37F5B8" name="X804B2E0F7E37F5B8"></a></p>
<h5>4.2-9 FixedStates</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FixedStates</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A list of FR elements describing the action of <var class="Arg">e</var> at fixed vertices.</p>
<p>This function calls repeatedly <code class="func">State</code> (<a href="chap4.html#X819E3E3080297347"><b>4.2-7</b></a>) to compute all the states of <var class="Arg">e</var> at non-trivial fixed vertices.</p>
<p><var class="Arg">e</var> 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 <var class="Arg">e</var>.</p>
<p>The ordering of the list is as follows. First come <var class="Arg">e</var>, or all elements of <var class="Arg">e</var>. Then come the states reached by <var class="Arg">e</var> in one transition, ordered by the alphabet letter leading to them; then come those reached in two transitions, ordered lexicographically by the transition; etc.</p>
<p>Note that this function is not guaranteed to terminate, if <var class="Arg">e</var> is not finite-state.</p>
<table class="example">
<tr><td><pre>
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> ]
</pre></td></tr></table>
<p><a id="X8303B36C83371FB3" name="X8303B36C83371FB3"></a></p>
<h5>4.2-10 LimitStates</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LimitStates</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A set of FR element describing the recurring actions of <var class="Arg">e</var> on all subtrees.</p>
<p>This function computes the <code class="func">States</code> (<a href="chap4.html#X7B0C97BC7C3BA20D"><b>4.2-8</b></a>) S of <var class="Arg">e</var>, and then repeatedly removes elements that are not <em>recurrent</em>, 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.</p>
<p>As for <code class="func">States</code> (<a href="chap4.html#X7B0C97BC7C3BA20D"><b>4.2-8</b></a>), <var class="Arg">e</var> may be either an FR element, or a list of FR elements.</p>
<p>Note that this function is not guaranteed to terminate. It currently terminates if and only if <code class="func">States</code> (<a href="chap4.html#X7B0C97BC7C3BA20D"><b>4.2-8</b></a>) terminates.</p>
<table class="example">
<tr><td><pre>
gap> m := FRMachine(["a","b"],[[[],[2]],[[],[1]]],[(1,2),()]);;
gap> a := FRElement(m,1);; b := FRElement(m,2);;
gap> LimitStates(a);
[ <2|a>, <2|identity ...>, <2|b> ]
gap> LimitStates(a^2);
[ <2|b>, <2|identity ...>, <2|a> ]
</pre></td></tr></table>
<p><a id="X7C4076707CBBE945" name="X7C4076707CBBE945"></a></p>
<h5>4.2-11 IsFiniteStateFRElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsFiniteStateFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( property )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsFiniteStateFRMachine</code>( <var class="Arg">e</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">e</var> is a finite-state element.</p>
<p>This function tests whether <var class="Arg">e</var> is a finite-state element.</p>
<p>When applied to a Mealy element, it returns <code class="keyw">true</code>.</p>
<table class="example">
<tr><td><pre>
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
</pre></td></tr></table>
<p><a id="X79E65E818690B4EB" name="X79E65E818690B4EB"></a></p>
<h5>4.2-12 InitialState</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> InitialState</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The initial state of an FR element.</p>
<p>This function returns the initial state of an FR element. It is an element of the stateset of the underlying FR machine of <var class="Arg">e</var>.</p>
<table class="example">
<tr><td><pre>
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
</pre></td></tr></table>
<p><a id="X823B6E3D819432D6" name="X823B6E3D819432D6"></a></p>
<h5>4.2-13 \^</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> \^</code>( <var class="Arg">e, v</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>The image of a vertex <var class="Arg">v</var> under <var class="Arg">e</var>.</p>
<p>This function accepts an FR element and a vertex <var class="Arg">v</var>, which is either an integer or a list. It returns the image of <var class="Arg">v</var> under the transformation <var class="Arg">e</var>, in the same format (integer/list) as <var class="Arg">v</var>.</p>
<p>The list <var class="Arg">v</var> can be a periodic list (see <code class="func">PeriodicList</code> (<a href="chap12.html#X7B401DFE817D3927"><b>12.1-6</b></a>)). In that case, the result in again a periodic list. The computation will succeed only if the states along the period are again periodic.</p>
<table class="example">
<tr><td><pre>
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 ] ]
</pre></td></tr></table>
<p><a id="X7C3CF6AF86336EDC" name="X7C3CF6AF86336EDC"></a></p>
<h5>4.2-14 \*</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> \*</code>( <var class="Arg">m, n</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>The product of the two FR elements <var class="Arg">m</var> and <var class="Arg">n</var>.</p>
<p>This function returns a new FR element, which is the product of the FR elements <var class="Arg">m</var> and <var class="Arg">n</var>.</p>
<p>In case <var class="Arg">m</var> and <var class="Arg">n</var> have the same underlying machine, this is the machine of the result. In case the machine of <var class="Arg">n</var> embeds in the machine of <var class="Arg">m</var> (see <code class="func">SubFRMachine</code> (<a href="chap3.html#X811B5BF17A3FE577"><b>3.5-9</b></a>)), the machine of the product is the machine of <var class="Arg">m</var>. In case the machine of <var class="Arg">m</var> embeds in the machine of <var class="Arg">n</var>, the machine of the product is the machine of <var class="Arg">n</var>. Otherwise the machine of the product is the product of the machines of <var class="Arg">m</var> and <var class="Arg">n</var> (See <code class="func">\*</code> (<a href="chap3.html#X7857704878577048"><b>3.5-3</b></a>)).</p>
<table class="example">
<tr><td><pre>
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 ]
</pre></td></tr></table>
<p><a id="X78C19ACA78F9F067" name="X78C19ACA78F9F067"></a></p>
<h5>4.2-15 \[\]</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> \[\]</code>( <var class="Arg">m, i</var> )</td><td class="tdright">( method )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> \{\}</code>( <var class="Arg">m, l</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>A [list of] FR element[s] with initial state <var class="Arg">i</var>.</p>
<p>These are respectively synonyms for <code class="code">FRElement(m,i)</code> and <code class="code">List(l,s->FRElement(m,s))</code>. The argument <var class="Arg">m</var> must be an FR machine, <var class="Arg">i</var> must be a positive integer, and <var class="Arg">l</var> must be a list.</p>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap3.html">Previous Chapter</a> <a href="chap5.html">Next Chapter</a> </div>
<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a> <a href="chap1.html">1</a> <a href="chap2.html">2</a> <a href="chap3.html">3</a> <a href="chap4.html">4</a> <a href="chap5.html">5</a> <a href="chap6.html">6</a> <a href="chap7.html">7</a> <a href="chap8.html">8</a> <a href="chap9.html">9</a> <a href="chap10.html">10</a> <a href="chap11.html">11</a> <a href="chap12.html">12</a> <a href="chapBib.html">Bib</a> <a href="chapInd.html">Ind</a> </div>
<hr />
<p class="foot">generated by <a href="http://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
91213ddcfbe7f54821d42c2d9e091326
>
files
>
1160
