<?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 3: Functionally recursive machines</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="chap2.html">Previous Chapter</a> <a href="chap4.html">Next Chapter</a> </div>
<p><a id="X7D65CA8B876E514C" name="X7D65CA8B876E514C"></a></p>
<div class="ChapSects"><a href="chap3.html#X7D65CA8B876E514C">3 <span class="Heading">Functionally recursive machines</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X7D52F7ED83E2D153">3.1 <span class="Heading">Types of machines</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X7EB36FBB78F4F26A">3.2 <span class="Heading">Products of machines</span></a>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X828640667D2E5280">3.3 <span class="Heading">Creators for <code class="code">FRMachine</code>s</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X80D310EF7FD5EA44">3.3-1 FRMachineNC</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X808F3BD97EDA8CE8">3.3-2 FRMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7C383F4383D22BFC">3.3-3 UnderlyingFRMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7BF186227C0ABE8D">3.3-4 AsGroupFRMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X814F53B97C3F43F5">3.3-5 ChangeFRMachineBasis</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X8753FA157B2AD6DC">3.4 <span class="Heading">Attributes for <code class="code">FRMachine</code>s</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8000470D7DA7FFBD">3.4-1 StateSet</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7F77F5DD789FA2F4">3.4-2 GeneratorsOfFRMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X80B52A8A7F30878E">3.4-3 Output</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7AEE87BC8393FA54">3.4-4 Transition</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7D95D1498586E5D0">3.4-5 WreathRecursion</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap3.html#X8158A8307CA98A3D">3.5 <span class="Heading">Operations for <code class="code">FRMachine</code>s</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8289C2F77D67EDC3">3.5-1 StructuralGroup</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7F2703417F270341">3.5-2 \+</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7857704878577048">3.5-3 \*</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7C0677148107F7FE">3.5-4 TensorSumOp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X8077C8A47E22FCB5">3.5-5 TensorProductOp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7D248C737D29A7CC">3.5-6 DirectSumOp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X81456F10820CAC87">3.5-7 DirectProductOp</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7A0858097AA3FBDA">3.5-8 TreeWreathProduct</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X811B5BF17A3FE577">3.5-9 SubFRMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X81B382BD81B2BD34">3.5-10 Minimized</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap3.html#X7C107A42815F91DA">3.5-11 Correspondence</a></span>
</div>
</div>
<h3>3 <span class="Heading">Functionally recursive machines</span></h3>
<p>At the core of this package are <em>functionally recursive machines</em>. The internals of machine will be described later, but each machine M has an associated <em>alphabet</em> X, a <em>set of states</em> Q, and a <em>transition function</em> phi:Q x X -> X x Q. An <em>element</em>, as we will see in Section <a href="chap4.html#X863D82207A1320F1"><b>4</b></a>, is given by a machine and an initial state qin Q.</p>
<p>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_2dots x_n with nge0, compute phi(q,x_1)=(y_1,r); then compute the action of (M,r) on the string x_2dots x_n, and call the result y_2dots y_n. Then the action of (M,q) on x_1x_2dots x_n yields y_1y_2dots y_n.</p>
<p>This can be understood more formally as follows. The transition function phi induces a map phi^n:Qx X^n -> X^n x 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^mx X^n -> X^n x Q^m.</p>
<p>We see that the action on finite strings preserves their length, and also preserves prefixes: if (M,q) maps x_1dots x_n to y_1dots y_m, then necessarily m=n; and if k<n then T maps x_1dots x_k to y_1dots y_k.</p>
<p>The strings over the alphabet X can be naturally organised into a rooted tree. The root represents the empty string, and the strings x_1dots x_n and x_1dots x_n+1 are connected by an edge, for all x_iin X.</p>
<p><a id="X7D52F7ED83E2D153" name="X7D52F7ED83E2D153"></a></p>
<h4>3.1 <span class="Heading">Types of machines</span></h4>
<p>Machines must be accessible to computation; therefore it is reasonable to assume that their alphabet X is finite.</p>
<p>If the stateset Q is also finite, the machine is called a <em>Mealy machine</em>, and its transition function phi can be stored as a table.</p>
<p>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 Sx X. Its values are then extended naturally by composition.</p>
<p>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, <code class="code">PermList(output[state])</code> gives the action on the first level.</p>
<p>Because of the way <strong class="pkg">GAP</strong> handles permutations and transformations, a permutation is never equal to a transformation, even though both can answer <code class="keyw">true</code> to IsOne. Therefore, <strong class="pkg">FR</strong> introduces a new type of transformation, which can be equal to a permutation, and which is actually represented as a permutation is it is invertible. Like permutations, the new transformations do not have a fixed degree. They are created by <code class="code">Trans(list)</code>.</p>
<p><a id="X7EB36FBB78F4F26A" name="X7EB36FBB78F4F26A"></a></p>
<h4>3.2 <span class="Heading">Products of machines</span></h4>
<p>Machines can be combined in different manners. If two machines act on the same alphabet, then their <em>sum</em> and <em>product</em> 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.</p>
<p>If a non-empty collection of machines have same stateset, then their <em>tensor sum</em> and <em>tensor product</em> 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.</p>
<p>The <em>direct sum</em> and <em>direct product</em> 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.</p>
<p><a id="X828640667D2E5280" name="X828640667D2E5280"></a></p>
<h4>3.3 <span class="Heading">Creators for <code class="code">FRMachine</code>s</span></h4>
<p><a id="X80D310EF7FD5EA44" name="X80D310EF7FD5EA44"></a></p>
<h5>3.3-1 FRMachineNC</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FRMachineNC</code>( <var class="Arg">fam, free, transitions, outputs</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new FR machine.</p>
<p>This function constructs a new FR machine, 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>.</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 also a list of lists; <var class="Arg">outputs</var>[<var class="Arg">s</var>][<var class="Arg">x</var>] is the output produced by the machine is in state <var class="Arg">s</var> and inputs <var class="Arg">x</var>.</p>
<table class="example">
<tr><td><pre>
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 ] )>
</pre></td></tr></table>
<p><a id="X808F3BD97EDA8CE8" name="X808F3BD97EDA8CE8"></a></p>
<h5>3.3-2 FRMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FRMachine</code>( <var class="Arg">[names, ]transitions, outputs</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">> FRMachine</code>( <var class="Arg">free, transitions, outputs</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new FR machine.</p>
<p>This function constructs a new FR machine. It has stateset a free group/semigroup/monoid, and structure described by <var class="Arg">transitions</var> and <var class="Arg">outputs</var>.</p>
<p>If there is an argument <var class="Arg">free</var>, it is the free group/monoid/semigroup to be used as stateset. Otherwise, the stateset will be guessed from the <var class="Arg">transitions</var> and <var class="Arg">outputs</var>; it will be a free group if all states are invertible, and a monoid otherwise. <var class="Arg">names</var> is then an optional list, with at position <var class="Arg">s</var> a string naming generator <var class="Arg">s</var> of the stateset. If <var class="Arg">names</var> contains too few entries, they are completed by the names <var class="Arg">__1,__2,...</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 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 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.</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 integers (the images of a transformation), describing the activity of state <var class="Arg">s</var>. 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.</p>
<table class="example">
<tr><td><pre>
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
</pre></td></tr></table>
<p><a id="X7C383F4383D22BFC" name="X7C383F4383D22BFC"></a></p>
<h5>3.3-3 UnderlyingFRMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> UnderlyingFRMachine</code>( <var class="Arg">obj</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>An FR machine underlying <var class="Arg">obj</var>.</p>
<p>FR elements, FR groups etc. often have an underlying FR machine, which is returned by this command.</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> UnderlyingFRMachine(a)=m;
true
</pre></td></tr></table>
<p><a id="X7BF186227C0ABE8D" name="X7BF186227C0ABE8D"></a></p>
<h5>3.3-4 AsGroupFRMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsGroupFRMachine</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsMonoidFRMachine</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsSemigroupFRMachine</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>An FR machine isomorphic to <var class="Arg">m</var>, on a free group.</p>
<p>This function constructs, from the FR machine <var class="Arg">m</var>, an isomorphic FR machine <code class="code">n</code> with a free group/monoid/semigroup as stateset. The attribute <code class="code">Correspondence(n)</code> is a mapping (homomorphism or list) from the stateset of <var class="Arg">m</var> to the stateset of <code class="code">n</code>.</p>
<table class="example">
<tr><td><pre>
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 ]
</pre></td></tr></table>
<p><a id="X814F53B97C3F43F5" name="X814F53B97C3F43F5"></a></p>
<h5>3.3-5 ChangeFRMachineBasis</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ChangeFRMachineBasis</code>( <var class="Arg">m[, l]</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>An equivalent FR machine, in a new basis.</p>
<p>This function constructs a new group FR machine, given a group FR machine <var class="Arg">m</var> and a list of states <var class="Arg">l</var> (as elements of the free object <code class="code">StateSet(m)</code>).</p>
<p>The new machine has the following transitions: if alphabet letter <code class="code">a</code> is mapped to <code class="code">b</code> by state <code class="code">s</code> in <var class="Arg">m</var>, leading to state <code class="code">t</code>, then in the new machine the new state is <code class="code">l[a]^-1*t*l[b]</code>.</p>
<p>The group generated by the new machine is isomorphic to the group generated by <var class="Arg">m</var>. This command amounts to a change of basis of the associated bimodule (see <a href="chapBib.html#biBMR2162164">[Nek05, Section 2.2]</a>). It amounts to conjugation by the automorphism <code class="code">c=FRElement("c",[l[1]*c,...,l[n]*c],[()],1)</code>.</p>
<p>If the second argument is absent, this command attempts to choose one that makes many entries of the recursion trivial.</p>
<table class="example">
<tr><td><pre>
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
-----+--------+--------------------+
</pre></td></tr></table>
<p><a id="X8753FA157B2AD6DC" name="X8753FA157B2AD6DC"></a></p>
<h4>3.4 <span class="Heading">Attributes for <code class="code">FRMachine</code>s</span></h4>
<p><a id="X8000470D7DA7FFBD" name="X8000470D7DA7FFBD"></a></p>
<h5>3.4-1 StateSet</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> StateSet</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The set of states associated with <var class="Arg">m</var>.</p>
<p>This function returns the stateset of <var class="Arg">m</var>. It can be either a list (if the machine is of Mealy type), or a free group/semigroup/monoid (in all other cases).</p>
<table class="example">
<tr><td><pre>
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 ]
</pre></td></tr></table>
<p><a id="X7F77F5DD789FA2F4" name="X7F77F5DD789FA2F4"></a></p>
<h5>3.4-2 GeneratorsOfFRMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GeneratorsOfFRMachine</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The generating set of the stateset of <var class="Arg">m</var>.</p>
<p>This function returns the generating set of the stateset of <var class="Arg">machine</var>. If <var class="Arg">m</var> is a Mealy machine, it returs the stateset.</p>
<table class="example">
<tr><td><pre>
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 ]
</pre></td></tr></table>
<p><a id="X80B52A8A7F30878E" name="X80B52A8A7F30878E"></a></p>
<h5>3.4-3 Output</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Output</code>( <var class="Arg">m, s</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">> Output</code>( <var class="Arg">m, s, x</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A transformation of <var class="Arg">m</var>'s alphabet.</p>
<p>This function returns the transformation of <var class="Arg">m</var>'s alphabet associated with state <var class="Arg">s</var>. This transformation is returned as a list of images.</p>
<p><var class="Arg">s</var> is also allowed to be a list, in which case it is interpreted as the corresponding product of states.</p>
<p>In the second form, the result is actually the image of <var class="Arg">x</var> under <code class="code">Output(m,s)</code>.</p>
<table class="example">
<tr><td><pre>
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]
</pre></td></tr></table>
<p><a id="X7AEE87BC8393FA54" name="X7AEE87BC8393FA54"></a></p>
<h5>3.4-4 Transition</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Transition</code>( <var class="Arg">m, s, i</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>An element of <var class="Arg">m</var>'s stateset.</p>
<p>This function returns the state reached by <var class="Arg">m</var> when started in state <var class="Arg">s</var> and 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> 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
</pre></td></tr></table>
<p><a id="X7D95D1498586E5D0" name="X7D95D1498586E5D0"></a></p>
<h5>3.4-5 WreathRecursion</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> WreathRecursion</code>( <var class="Arg">machine</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A function on the stateset of <var class="Arg">machine</var>.</p>
<p>This function returns a function on <var class="Arg">machine</var>'s stateset. This function, on receiving state <var class="Arg">q</var> as input, returns a list. Its first entry is a list indexed by <var class="Arg">machine</var>'s alphabet, with in position <var class="Arg">x</var> the state <var class="Arg">machine</var> would be in if it received input <var class="Arg">x</var> when in state <var class="Arg">q</var>. The second entry is the list of the permutation of <var class="Arg">machine</var>'s alphabet induced by <var class="Arg">q</var>.</p>
<p><var class="Arg">WreathRecursion(machine)(q)[1][a]</var> is equal to <var class="Arg">Transition(machine,q,a)</var> and <var class="Arg">WreathRecursion(machine)(q)[2]</var> is equal to <var class="Arg">Output(machine,q)</var>.</p>
<table class="example">
<tr><td><pre>
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] ]
</pre></td></tr></table>
<p><a id="X8158A8307CA98A3D" name="X8158A8307CA98A3D"></a></p>
<h4>3.5 <span class="Heading">Operations for <code class="code">FRMachine</code>s</span></h4>
<p><a id="X8289C2F77D67EDC3" name="X8289C2F77D67EDC3"></a></p>
<h5>3.5-1 StructuralGroup</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> StructuralGroup</code>( <var class="Arg">machine</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">> StructuralMonoid</code>( <var class="Arg">machine</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">> StructuralSemigroup</code>( <var class="Arg">machine</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A finitely presented group/monoid/semigroup capturing the structure of <var class="Arg">machine</var>.</p>
<p>This function returns a finitely presented group/monoid/semigroup, with generators the union of the <code class="func">AlphabetOfFRObject</code> (<a href="chap11.html#X7BC9CD3685C26823"><b>11.1-3</b></a>) and <code class="func">GeneratorsOfFRMachine</code> (<a href="chap3.html#X7F77F5DD789FA2F4"><b>3.4-2</b></a>) of <var class="Arg">machine</var>, and relations all qa'=aq' whenever phi(q,a)=(a',q').</p>
<table class="example">
<tr><td><pre>
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 ]
</pre></td></tr></table>
<p><a id="X7F2703417F270341" name="X7F2703417F270341"></a></p>
<h5>3.5-2 \+</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> \+</code>( <var class="Arg">machine1, machine2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>A new FR machine, in the same family as its arguments.</p>
<p>This function returns a new FR machine, with stateset generated by the union of the statesets of its arguments. The arguments <var class="Arg">machine1</var> and <var class="Arg">machine2</var> must operate on the same alphabet. If the stateset of <var class="Arg">machine1</var> is free on n_1 letters and the stateset of <var class="Arg">machine2</var> 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 <var class="Arg">machine1</var>'s states and the next n_2 with <var class="Arg">machine2</var>'s.</p>
<p>The transition and output functions are naturally extended to the sum.</p>
<p>The arguments may be free groups, semigroups 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.</p>
<p>The maps from the stateset of <var class="Arg">machine1</var> or <var class="Arg">machine2</var> to the stateset of the result <code class="code">r</code> can be recovered as <code class="code">Correspondence(r)[1]</code> and <code class="code">Correspondence(r)[2]</code>; see <code class="func">Correspondence</code> (<a href="chap3.html#X7C107A42815F91DA"><b>3.5-11</b></a>).</p>
<table class="example">
<tr><td><pre>
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
</pre></td></tr></table>
<p><a id="X7857704878577048" name="X7857704878577048"></a></p>
<h5>3.5-3 \*</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> \*</code>( <var class="Arg">machine1, machine2</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>A new FR machine, in the same family as its arguments.</p>
<p>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 <code class="func">\+</code> (<a href="chap3.html#X7F2703417F270341"><b>3.5-2</b></a>).</p>
<p><a id="X7C0677148107F7FE" name="X7C0677148107F7FE"></a></p>
<h5>3.5-4 TensorSumOp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TensorSumOp</code>( <var class="Arg">FR_machines, machine</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>A new FR machine on the disjoint union of the arguments' alphabets.</p>
<p>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 <code class="code">[1..n1]</code> up to <code class="code">[1..nk]</code>, then the alphabet of their sum is <code class="code">[1..n1+...+nk]</code> and the transition functions are similarly concatenated.</p>
<p>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.</p>
<table class="example">
<tr><td><pre>
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
---+-----+-----+-----+-----+-----+-----+-----+-----+-----+
</pre></td></tr></table>
<p><a id="X8077C8A47E22FCB5" name="X8077C8A47E22FCB5"></a></p>
<h5>3.5-5 TensorProductOp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TensorProductOp</code>( <var class="Arg">FR, machines, machine</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>A new FR machine on the cartesian product of the arguments' alphabets.</p>
<p>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.</p>
<p>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.</p>
<p>Due to an overloading problem in the GAP library, the user-level command is temporarily renamed <code class="code">TensorProductX</code>.</p>
<table class="example">
<tr><td><pre>
gap> m := TensorProductX(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
---+-----+-----+-----+-----+-----+-----+
</pre></td></tr></table>
<p><a id="X7D248C737D29A7CC" name="X7D248C737D29A7CC"></a></p>
<h5>3.5-6 DirectSumOp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DirectSumOp</code>( <var class="Arg">FR, machines, machine</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>A new FR machine on the disjoint union of the arguments' alphabets.</p>
<p>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 <code class="code">[1..n1]</code> up to <code class="code">[1..nk]</code>, then the alphabet of their sum is <code class="code">[1..n1+...+nk]</code> and the output and transition functions are similarly concatenated.</p>
<p>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.</p>
<table class="example">
<tr><td><pre>
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
---+-----+-----+-----+-----+-----+-----+-----+-----+-----+
</pre></td></tr></table>
<p><a id="X81456F10820CAC87" name="X81456F10820CAC87"></a></p>
<h5>3.5-7 DirectProductOp</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DirectProductOp</code>( <var class="Arg">FR, machines, machine</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>A new FR machine on the cartesian product of the arguments' alphabets.</p>
<p>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 <code class="code">[1..n1]</code> up to <code class="code">[1..nk]</code>, then the alphabet of their product is <code class="code">[1..n1*...*nk]</code> and the output and transition functions act component-wise.</p>
<p>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.</p>
<table class="example">
<tr><td><pre>
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
---+-----+-----+-----+-----+-----+-----+
</pre></td></tr></table>
<p><a id="X7A0858097AA3FBDA" name="X7A0858097AA3FBDA"></a></p>
<h5>3.5-8 TreeWreathProduct</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TreeWreathProduct</code>( <var class="Arg">m, n, x0, y0</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p><b>Returns: </b>A new FR machine on the cartesian product of the arguments' alphabets.</p>
<p>The <em>tree-wreath product</em> 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.</p>
<p>It is introduced (in lesser generality, and with small variations) in <a href="chapBib.html#biBMR2197828">[Sid05]</a>, and may be described as follows: one takes two copies of the stateset of <var class="Arg">m</var>, one copy of the stateset of <var class="Arg">n</var>, and, if necessary, an extra identity state.</p>
<p>The first copy of <var class="Arg">m</var> fixes the alphabet Xx 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 <var class="Arg">m</var> 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 <var class="Arg">m</var> therefore acts only in the X direction, on the subtree (Xx{y0})^infty, on subtrees below vertices of the form (x0,y0)^t(x,y0).</p>
<p>A state t in the copy of <var class="Arg">n</var> 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'.</p>
<table class="example">
<tr><td><pre>
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
---+-----+-----+-----+-----+-----+-----+
</pre></td></tr></table>
<p><a id="X811B5BF17A3FE577" name="X811B5BF17A3FE577"></a></p>
<h5>3.5-9 SubFRMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> SubFRMachine</code>( <var class="Arg">machine1, machine2</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>Either <code class="keyw">fail</code> or an embedding of the states of <var class="Arg">machine2</var> in the states of <var class="Arg">machine1</var>.</p>
<p>This function attempts to locate a copy of <var class="Arg">machine2</var> in <var class="Arg">machine1</var>. If is succeeds, it returns a homomorphism from the stateset of <var class="Arg">machine2</var> into the stateset of <var class="Arg">machine1</var>; otherwise it returns <code class="keyw">fail</code>.</p>
<table class="example">
<tr><td><pre>
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 ]
</pre></td></tr></table>
<p><a id="X81B382BD81B2BD34" name="X81B382BD81B2BD34"></a></p>
<h5>3.5-10 Minimized</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Minimized</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A minimized machine equivalent to <var class="Arg">m</var>.</p>
<p>This function attempts to construct a machine equivalent to <var class="Arg">m</var>, but with a stateset of smaller rank. Identical generators are collapsed to a single generator of the stateset; if <var class="Arg">m</var> is a group or monoid machine then trivial generators are removed; if <var class="Arg">m</var> is a group machine then mutually inverse generators are grouped. This function sets as <code class="code">Correspondence(result)</code> a mapping between the stateset of <var class="Arg">m</var> and the stateset of the result; see <code class="func">Correspondence</code> (<a href="chap3.html#X7C107A42815F91DA"><b>3.5-11</b></a>).</p>
<table class="example">
<tr><td><pre>
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 ]
</pre></td></tr></table>
<p><a id="X7C107A42815F91DA" name="X7C107A42815F91DA"></a></p>
<h5>3.5-11 Correspondence</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Correspondence</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A mapping between statesets of FR machines.</p>
<p>If a machine <var class="Arg">m</var> was created as a minimized group/monoid/semigroup machine, then <code class="code">Correspondence(m)</code> is a mapping between the stateset of the original machine and the stateset of <var class="Arg">m</var>. See <code class="func">Minimized</code> (<a href="chap3.html#X81B382BD81B2BD34"><b>3.5-10</b></a>) for an example.</p>
<p>If <var class="Arg">m</var> was created as a minimized Mealy machine, then <code class="code">Correspondence(m)</code> 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 <code class="func">Minimized</code> (<a href="chap5.html#X8395542D846FA2B9"><b>5.2-2</b></a>) for an example.</p>
<p>If <var class="Arg">m</var> was created using <code class="func">AsGroupFRMachine</code> (<a href="chap3.html#X7BF186227C0ABE8D"><b>3.3-4</b></a>), <code class="func">AsMonoidFRMachine</code> (<a href="chap3.html#X7BF186227C0ABE8D"><b>3.3-4</b></a>), <code class="func">AsSemigroupFRMachine</code> (<a href="chap3.html#X7BF186227C0ABE8D"><b>3.3-4</b></a>), or <code class="func">AsMealyMachine</code> (<a href="chap5.html#X79EFE2C97D2CCEEC"><b>5.2-18</b></a>), then <code class="code">Correspondence(m)</code> 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.</p>
<p>If <var class="Arg">m</var> was created as a sum of two machines, then <var class="Arg">m</var> has a mapping <code class="code">Correspondence(m)[i]</code> between the stateset of machine <code class="code">i=1,2</code> and its own stateset. See <code class="func">\+</code> (<a href="chap3.html#X7F2703417F270341"><b>3.5-2</b></a>) for an example.</p>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap2.html">Previous Chapter</a> <a href="chap4.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
>
1158
