<?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 5: Mealy machines and 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="chap4.html">Previous Chapter</a> <a href="chap6.html">Next Chapter</a> </div>
<p><a id="X7C77EBC17DEF4CF6" name="X7C77EBC17DEF4CF6"></a></p>
<div class="ChapSects"><a href="chap5.html#X7C77EBC17DEF4CF6">5 <span class="Heading">Mealy machines and elements</span></a>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X846B89F686B50AE1">5.1 <span class="Heading">Creators for <code class="code">MealyMachine</code>s and <code class="code">MealyElement</code>s</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7EF3E00080624B70">5.1-1 MealyMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X875B8FED7FD20FA1">5.1-2 MealyMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8578657C7F4B6254">5.1-3 MealyMachineNC</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X83BBE01884D6E315">5.1-4 AllMealyMachines</a></span>
</div>
<div class="ContSect"><span class="nocss"> </span><a href="chap5.html#X7F673D877B205708">5.2 <span class="Heading">Operations and Attributes for <code class="code">MealyMachine</code>s and <code class="code">MealyElement</code>s</span></a>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7DF9F3AD86602DFC">5.2-1 Draw</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8395542D846FA2B9">5.2-2 Minimized</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X809F069B798ED985">5.2-3 DualMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7D5D480C782FCC0B">5.2-4 IsReversible</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8310A1C08158793C">5.2-5 IsMinimized</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7CCB79B981912CCC">5.2-6 AlphabetInvolution</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X80D2545D7D0990A2">5.2-7 IsBireversible</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X83364DAB825D7A0D">5.2-8 StateGrowth</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X84BE780A81CAC69C">5.2-9 Degree</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X793C427084F830CE">5.2-10 IsFinitaryFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7E5E8B2C79688DC0">5.2-11 Depth</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X82F4410E85C54C7E">5.2-12 IsBoundedFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X81D4A3F27C5FAD96">5.2-13 IsPolynomialGrowthFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7ECE17387910C023">5.2-14 Signatures</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X83DFDC3384EA4634">5.2-15 VertexTransformationsFRMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7E0CB3767CE08692">5.2-16 FixedRay</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X828C167B7D7691E9">5.2-17 IsLevelTransitive</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X79EFE2C97D2CCEEC">5.2-18 AsMealyMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X80F9A18483F98442">5.2-19 AsMealyMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7FB3F0A2878DD2CF">5.2-20 AsMealyElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7FBBBD9A839011C8">5.2-21 AsIntMealyMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X8191456B7E586785">5.2-22 TopElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7A87ED9D789245E4">5.2-23 ConfinalityClasses</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X81592E3D79745A40">5.2-24 Germs</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7F76AF2D7C0279F9">5.2-25 HasOpenSetConditionFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X82308064814FEA51">5.2-26 LimitMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7F8163B5816969C8">5.2-27 NucleusMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5.html#X7B29565784A591EC">5.2-28 GuessMealyElement</a></span>
</div>
</div>
<h3>5 <span class="Heading">Mealy machines and elements</span></h3>
<p><em>Mealy machines</em> form a special class of FR machines. They have as stateset a finite set, as opposed to a free group/monoid/semigroup. All commands available for FR machines are also available for Mealy machines, but the latter have added functionality.</p>
<p>There are currently two types of Mealy machines; one has as stateset an interval of integers of the form <code class="code">[1..m]</code> and as alphabet a set of integers; the other has an arbitrary domain as stateset and alphabet. Almost no functionality is implemented for the latter type, but there is a function converting it to the former type (see <code class="func">AsMealyMachine</code> (<a href="chap5.html#X79EFE2C97D2CCEEC"><b>5.2-18</b></a>)).</p>
<p>The internal representation of a Mealy machine of the first kind is quite different from that of FR machines. The alphabet is assumed to be an interval <code class="code">[1..n]</code>, and the stateset is assumed to be an interval <code class="code">[1..m]</code>. The transitions are stored as a m x n matrix, and the outputs are stored in a list of length m, consisting of permutations or transformations.</p>
<p>Mealy machines have additional properties, in particular they can act on periodic sequences (see <code class="func">PeriodicList</code> (<a href="chap12.html#X7B401DFE817D3927"><b>12.1-6</b></a>)). For example, the periodic sequence <code class="code">PeriodicList([1],[1,2])</code> describes the infinite ray <code class="code">[1,1,2,1,2,..]</code> in the tree. In principle, Mealy machines could act on sequences accepted by an automaton, although this is not yet implemented.</p>
<p>Mealy elements are Mealy machines with an initial state. For efficiency reasons, Mealy elements are always minimized, and their states are ordered in a canonical top-down, left-to-right order of traversal of the tree. In particular, their initial state is always 1. In this implementation, multiplication of Mealy elements is slower than multiplication of group FR elements, while comparison of Mealy elements is faster than comparison of group FR elements. In practise, it is better to work with Mealy elements as often as possible.</p>
<p>Products of Mealy machines behave in the same way as products of general FR machines, see <a href="chap3.html#X7EB36FBB78F4F26A"><b>3.2</b></a>. The only difference is that now the sum and products of statesets are distinct; the sum of statesets being their disjoint union, and their product being their cartesian product.</p>
<p><a id="X846B89F686B50AE1" name="X846B89F686B50AE1"></a></p>
<h4>5.1 <span class="Heading">Creators for <code class="code">MealyMachine</code>s and <code class="code">MealyElement</code>s</span></h4>
<p><a id="X7EF3E00080624B70" name="X7EF3E00080624B70"></a></p>
<h5>5.1-1 MealyMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MealyMachine</code>( <var class="Arg">[alphabet, ]transitions, output</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">> MealyElement</code>( <var class="Arg">[alphabet, ]transitions, output, init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new Mealy machine/element.</p>
<p>This function constructs a new Mealy machine or element, of integer type.</p>
<p><var class="Arg">transitions</var> is a list of lists; <code class="code">transitions[s][x]</code> is an integer, 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">output</var> is a list; at position <var class="Arg">s</var> it contains a permutation, a transformation describing the activity of state <var class="Arg">s</var>, or a list describing the images of the transformation.</p>
<p><var class="Arg">alphabet</var> is an optional domain given as first argument; When present, it is assumed to be a finite domain, mapped bijectively to <code class="code">[1..n]</code> by its enumerator. The indices "<code class="code">[s]</code>" above are then understood with respect to this enumeration.</p>
<p><var class="Arg">init</var> is an integer describing the initial state the newly created Mealy element should be in.</p>
<table class="example">
<tr><td><pre>
gap> b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
gap> Display(b);
| 1 2
---+-----+-----+
a | c,2 b,1
b | c,1 a,2
c | c,1 c,2
---+-----+-----+
gap> n := MealyMachine(Domain([11,12]),[[3,2],[3,1],[3,3]],[(1,2),(),()]);
<Mealy machine on alphabet [ 11, 12 ] with states [ 1 .. 3 ]>
gap> Display(n);
| 11 12
---+------+------+
a | c,12 b,11
b | c,11 a,12
c | c,11 c,12
---+------+------+
</pre></td></tr></table>
<table class="example">
<tr><td><pre>
gap> tau := MealyElement([[2,1],[2,2]],[(1,2),()],1);
<Mealy machine on alphabet [ 1, 2 ] with 2 states, initial state 1>
gap> Display(tau);
| 1 2
---+-----+-----+
a | b,2 a,1
b | b,1 b,2
---+-----+-----+
Initial state: a
gap> [1,1]^tau; [[1]]^tau; [[2]]^tau;
[ 2, 1 ]
[ 2, [ 1 ] ]
[ [ 1 ] ]
</pre></td></tr></table>
<p><a id="X875B8FED7FD20FA1" name="X875B8FED7FD20FA1"></a></p>
<h5>5.1-2 MealyMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MealyMachine</code>( <var class="Arg">stateset, alphabet, transitions, output</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">> MealyElement</code>( <var class="Arg">stateset, alphabet, transitions, output, init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new Mealy machine/element.</p>
<p>This function constructs a new Mealy machine or element, of domain type.</p>
<p><var class="Arg">stateset</var> and <var class="Arg">alphabet</var> are domains; they are not necessarily finite.</p>
<p><var class="Arg">transitions</var> is a function; it takes as arguments a state and an alphabet letter, and returns a state.</p>
<p><var class="Arg">output</var> is either a function, accepting as arguments a state and a letter, and returning a letter.</p>
<p><var class="Arg">init</var> is an element of <var class="Arg">stateset</var> describing the initial state the newly created Mealy element should be in.</p>
<table class="example">
<tr><td><pre>
gap> g := Group((1,2));; n := MealyMachine(g,g,\*,\*);
<Mealy machine on alphabet [ (), (1,2) ] with states Group( [ (1,2) ] )>
gap> [(1,2),()]^FRElement(n,());
[ (1,2), (1,2) ]
gap> a := MealyElement(g,g,\*,\*,());
<Mealy machine on alphabet [ (), (1,2) ] with states Group(
[ (1,2) ] ), initial state ()>
gap> [(1,2),()]^a;
[ (1,2), (1,2) ]
</pre></td></tr></table>
<p><a id="X8578657C7F4B6254" name="X8578657C7F4B6254"></a></p>
<h5>5.1-3 MealyMachineNC</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> MealyMachineNC</code>( <var class="Arg">fam, transitions, output</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">> MealyElementNC</code>( <var class="Arg">fam, transitions, output, init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A new Mealy machine/element.</p>
<p>This function constructs a new Mealy machine or element, of integer type. No tests are performed to check that the arguments contain values within bounds, or even of the right type (beyond the simple checking performed by <strong class="pkg">GAP</strong>'s method selection algorithms). In particular, Mealy elements are always assumed to be minimized, but these functions leave this task to the user.</p>
<p><var class="Arg">fam</var> is the family to which the newly created Mealy machine will belong.</p>
<p><var class="Arg">transitions</var> is a list of lists; <code class="code">transitions[s][x]</code> is an integer, 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">output</var> is a list; at position <var class="Arg">s</var> it contains a permutation or a transformation describing the activity of state <var class="Arg">s</var>.</p>
<p><var class="Arg">init</var> is an integer describing the initial state the newly created Mealy element should be in.</p>
<table class="example">
<tr><td><pre>
gap> taum := MealyMachine([[2,1],[2,2]],[(1,2),()]);
<Mealy machine on alphabet [ 1, 2 ] with 2 states>
gap> tauminv := MealyMachineNC(FamilyObj(taum),[[1,2],[2,2]],[(1,2),()]);
<Mealy machine on alphabet [ 1, 2 ] with 2 states>
gap> tau := MealyElement([[2,1],[2,2]],[(1,2),()],1);
<Mealy machine on alphabet [ 1, 2 ] with 2 states, initial state 1>
gap> tauinv := MealyElementNC(FamilyObj(n),[[1,2],[2,2]],[(1,2),()],1);
<Mealy machine on alphabet [ 1, 2 ] with 2 states, initial state 1>
gap> tau=FRElement(taum,1); tauinv=FRElement(tauminv,1);
true
true
gap> IsOne(tau*tauinv);
true
</pre></td></tr></table>
<p><a id="X83BBE01884D6E315" name="X83BBE01884D6E315"></a></p>
<h5>5.1-4 AllMealyMachines</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AllMealyMachines</code>( <var class="Arg">m, n[, filters]</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p><b>Returns: </b>A list of all Mealy machines with specified properties.</p>
<p>This function constructs all mealy with alphabet <code class="code">[1..m]</code>, stateset <code class="code">[1..n]</code> and specified properties.</p>
<p>These properties are specified as additional arguments. They can include <code class="func">IsInvertible</code> (<a href="chap11.html#X83AEFB8184F4B023"><b>11.2-14</b></a>), <code class="func">IsReversible</code> (<a href="chap5.html#X7D5D480C782FCC0B"><b>5.2-4</b></a>), <code class="func">IsBireversible</code> (<a href="chap5.html#X80D2545D7D0990A2"><b>5.2-7</b></a>), and <code class="func">IsMinimized</code> (<a href="chap5.html#X8310A1C08158793C"><b>5.2-5</b></a>) to specify that the machines should have that property.</p>
<p>A group/monoid/semigroup <code class="code">p</code> may also be passed as argument; this specifies the allowable vertex transformations of the machines. The property <code class="code">IsTransitive</code> requires that the state-closed group/monoid/semigroup of the machine act transitively on its alphabet, and <code class="code">IsSurjective</code> requires that its <code class="func">VertexTransformationsFRMachine</code> (<a href="chap5.html#X83DFDC3384EA4634"><b>5.2-15</b></a>) be precisely equal to <code class="code">p</code>.</p>
<p>The argument <code class="code">EquivalenceClasses</code> returns one isomorphism class of Mealy machine, under the permutations of the stateset and alphabet.</p>
<p>The following example constructs the two Mealy machines <code class="func">AleshinMachine</code> (<a href="chap10.html#X7C286D3A84790ECE"><b>10.1-14</b></a>) and <code class="func">BabyAleshinMachine</code> (<a href="chap10.html#X7E024B4D7BA411B1"><b>10.1-15</b></a>):</p>
<table class="example">
<tr><td><pre>
gap> l := AllMealyMachines(2,3,IsBireversible,IsSurjective,EquivalenceClasses);;
gap> Length(l);
20
gap> Filtered(l,x->VertexTransformationsFRMachine(DualMachine(x))=SymmetricGroup(3)
> and Size(StateSet(Minimized(x)))=3);
[ <Mealy machine on alphabet [ 1, 2 ] with 3 states>,
<Mealy machine on alphabet [ 1, 2 ] with 3 states> ]
gap> Display(last[1]);
| 1 2
---+-----+-----+
a | a,1 b,2
b | c,2 c,1
c | b,1 a,2
---+-----+-----+
gap> Display(last[2]);
| 1 2
---+-----+-----+
a | a,2 b,1
b | c,1 c,2
c | b,2 a,1
---+-----+-----+
</pre></td></tr></table>
<p><a id="X7F673D877B205708" name="X7F673D877B205708"></a></p>
<h4>5.2 <span class="Heading">Operations and Attributes for <code class="code">MealyMachine</code>s and <code class="code">MealyElement</code>s</span></h4>
<p><a id="X7DF9F3AD86602DFC" name="X7DF9F3AD86602DFC"></a></p>
<h5>5.2-1 Draw</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Draw</code>( <var class="Arg">m[, filename]</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>This function creates a graph description of the Mealy machine/element <var class="Arg">m</var>. If a second argument <var class="Arg">filename</var> is present, the graph is saved, in <code class="keyw">dot</code> format, under that filename; otherwise it is converted to Postscript using the program <code class="keyw">dot</code> from the <strong class="pkg">graphviz</strong> package, and is displayed in a separate X window using the program <strong class="pkg">display</strong>. This works on UNIX systems.</p>
<p>A circle is displayed for every state of <var class="Arg">m</var>, and there is an edge for every transition in <var class="Arg">m</var>. It has label of the form x/y, where x is the input symbol and y is the corresponding output. Edges are coloured according to the input symbol, in the order "red", "blue", "green", "gray", "yellow", "cyan", "orange", "purple". If <var class="Arg">m</var> has an initial state, it is indicated as a doubly circled state.</p>
<p>If <var class="Arg">m</var> is a FR machine, <code class="code">Draw</code> first attempts to convert it to a Mealy machine (see <code class="func">AsMealyMachine</code> (<a href="chap5.html#X79EFE2C97D2CCEEC"><b>5.2-18</b></a>)).</p>
<p>It is assumed, but not checked, that <strong class="pkg">graphviz</strong> and <strong class="pkg">display</strong> are properly installed on the system.</p>
<p><a id="X8395542D846FA2B9" name="X8395542D846FA2B9"></a></p>
<h5>5.2-2 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 contructs the minimized Mealy machine <code class="code">r</code> corresponding to <var class="Arg">m</var>, by identifying isomorphic states; and, if <var class="Arg">m</var> is initial, by removing inaccessible states.</p>
<p>If <var class="Arg">m</var> is initial, the minimized automaton is such that its states are numbered first by distance to the initial state, and then lexicographically by input letter. (in particular, the initial state is 1). This makes comparison of minimized automata efficient.</p>
<p>Furthermore, <code class="code">Correspondence(r)</code> is a list describing, for each (accessible) state of <var class="Arg">m</var>, its corresponding state in <code class="code">r</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> GrigorchukMachine := MealyMachine([[2,3],[4,4],[2,5],[4,4],[4,1]],
[(),(1,2),(),(),()]);
<Mealy machine on alphabet [ 1, 2 ] with 5 states>
gap> g2 := GrigorchukMachine^2;
<Mealy machine on alphabet [ 1, 2 ] with 25 states>
gap> Minimized(g2);
<Mealy machine on alphabet [ 1, 2 ] with 11 states, minimized>
gap> Correspondence(last);
[ 2, 1, 4, 11, 9, 1, 2, 5, 7, 6, 4, 3, 2, 9, 11, 11, 10, 9, 2, 4, 9, 8, 11, 4, 2 ]
gap> e := FRElement(g2,11);
<Mealy element on alphabet [ 1, 2 ] with 25 states, initial state 11>
gap> Minimized(e);
<Mealy element on alphabet [ 1, 2 ] with 5 states, initial state 1, minimized>
gap> Correspondence(last);
[ 3, 2, 1, 4, 5, 2, 3,,,, 1,, 3, 5, 4, 4,, 5, 3, 1, 5,, 4, 1, 3 ]
</pre></td></tr></table>
<p><a id="X809F069B798ED985" name="X809F069B798ED985"></a></p>
<h5>5.2-3 DualMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> DualMachine</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The dual Mealy machine of <var class="Arg">m</var>.</p>
<p>This function constructs the <em>dual</em> machine of <var class="Arg">m</var>, i.e. the machine with stateset the alphabet of <var class="Arg">m</var>, with alphabet the stateset of <var class="Arg">m</var>, and similarly with transitions and output switched.</p>
<table class="example">
<tr><td><pre>
gap> b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
gap> d := DualMachine(b)^4);
<Mealy machine on alphabet [ 1, 2, 3 ] with 16 states>
gap> Draw(d); # action on 2^4 points
gap> DualMachine(d);
<Mealy machine on alphabet [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
] with 3 states>
gap> Output(last,1)=Activity(FRElement(b,1),4);
true
</pre></td></tr></table>
<p><a id="X7D5D480C782FCC0B" name="X7D5D480C782FCC0B"></a></p>
<h5>5.2-4 IsReversible</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsReversible</code>( <var class="Arg">m</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">m</var> is a reversible Mealy machine.</p>
<p>This function tests whether <var class="Arg">m</var> is <em>reversible</em>, i.e. whether the <code class="func">DualMachine</code> (<a href="chap5.html#X809F069B798ED985"><b>5.2-3</b></a>) of <var class="Arg">m</var> is invertible. See <a href="chapBib.html#biBMR1841119">[MNS00]</a> for more details.</p>
<table class="example">
<tr><td><pre>
gap> IsReversible(MealyMachine([[1,2],[2,2]],[(1,2),()]));
false
gap> IsReversible(MealyMachine([[1,2],[2,1]],[(),(1,2)]));
</pre></td></tr></table>
<p><a id="X8310A1C08158793C" name="X8310A1C08158793C"></a></p>
<h5>5.2-5 IsMinimized</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsMinimized</code>( <var class="Arg">m</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">m</var> is a minimized Mealy machine.</p>
<p>This function tests whether <var class="Arg">m</var> is <em>minimized</em>, i.e. whether nono of its states can be removed or coalesced. All Mealy elements are automatically minimized.</p>
<table class="example">
<tr><td><pre>
gap> AllMealyMachines(2, 2, IsBireversible,EquivalenceClasses);
[ <Mealy machine on alphabet [ 1, 2 ] with 2 states>,
<Mealy machine on alphabet [ 1, 2 ] with 2 states>,
<Mealy machine on alphabet [ 1, 2 ] with 2 states>,
<Mealy machine on alphabet [ 1, 2 ] with 2 states>,
<Mealy machine on alphabet [ 1, 2 ] with 2 states>,
<Mealy machine on alphabet [ 1, 2 ] with 2 states>,
<Mealy machine on alphabet [ 1, 2 ] with 2 states>,
<Mealy machine on alphabet [ 1, 2 ] with 2 states> ]
gap> List(last,IsMinimized);
[ false, true, false, false, false, false, true, false ]
</pre></td></tr></table>
<p><a id="X7CCB79B981912CCC" name="X7CCB79B981912CCC"></a></p>
<h5>5.2-6 AlphabetInvolution</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AlphabetInvolution</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A list giving, for each alphabet letter, its inverse.</p>
<p>If <var class="Arg">m</var> is a bireversible machine, it may happen that the stateset of the dual of <var class="Arg">m</var> (see <code class="func">DualMachine</code> (<a href="chap5.html#X809F069B798ED985"><b>5.2-3</b></a>)) is closed under taking inverses. If this happens, then this list records the mapping from an alphabet letter of <var class="Arg">m</var> to its inverse.</p>
<table class="example">
<tr><td><pre>
gap> m := GammaPQMachine(3,5);; AlphabetOfFRObject(m);
[ 1 .. 6 ]
gap> IsBireversible(m); AlphabetInvolution(GammaPQMachine(3,5));
true
[ 6, 5, 4, 3, 2, 1 ]
</pre></td></tr></table>
<p><a id="X80D2545D7D0990A2" name="X80D2545D7D0990A2"></a></p>
<h5>5.2-7 IsBireversible</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsBireversible</code>( <var class="Arg">m</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p><b>Returns: </b><code class="keyw">true</code> if <var class="Arg">m</var> is a bireversible Mealy machine.</p>
<p>This function tests whether <var class="Arg">m</var> is <em>bireversible</em>, i.e. whether all eight machines obtained from <var class="Arg">m</var> using <code class="func">DualMachine</code> (<a href="chap5.html#X809F069B798ED985"><b>5.2-3</b></a>) and <code class="code">Inverse</code> are well-defined. See <a href="chapBib.html#biBMR1841119">[MNS00]</a> for more details.</p>
<table class="example">
<tr><td><pre>
gap> IsBireversible(MealyMachine([[1,2],[2,1]],[(),(1,2)]));
false
gap> IsBireversible(MealyMachine([[1,1],[2,2]],[(),(1,2)]));
true
</pre></td></tr></table>
<p><a id="X83364DAB825D7A0D" name="X83364DAB825D7A0D"></a></p>
<h5>5.2-8 StateGrowth</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> StateGrowth</code>( <var class="Arg">m[, x]</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The state growth of the Mealy machine or element <var class="Arg">m</var>.</p>
<p>This function computes, as a rational function, the power series in <var class="Arg">x</var> whose coefficient of degree n is the number of non-trivial states at level n of the tree.</p>
<p>If <var class="Arg">x</var> is absent, it is assumed to be <code class="code">Indeterminate(Rationals)</code>.</p>
<p>If <var class="Arg">m</var> is a Mealy machine, this function is computed with respect to all possible starting states. If <var class="Arg">m</var> is a Mealy element, this function is computed with respect to the initial state of <var class="Arg">m</var>.</p>
<table class="example">
<tr><td><pre>
gap> b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
gap> StateGrowth(b,Indeterminate(Rationals));
(2)/(-x_1+1)
gap> StateGrowth(FRElement(b,1),Indeterminate(Rationals));
(1)/(-x_1+1)
</pre></td></tr></table>
<p><a id="X84BE780A81CAC69C" name="X84BE780A81CAC69C"></a></p>
<h5>5.2-9 Degree</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Degree</code>( <var class="Arg">m</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">> DegreeOfFRMachine</code>( <var class="Arg">m</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">> DegreeOfFRElement</code>( <var class="Arg">m</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The growth degree of the Mealy machine or element <var class="Arg">m</var>.</p>
<p>This function computes the order of the pole at x=1 of <code class="code">StateGrowth(m,x)</code>, in case its denominator is a product of cyclotomics; and returns <code class="keyw">infinity</code> otherwise.</p>
<p>This attribute of Mealy machines was studied inter alia in <a href="chapBib.html#biBMR1774362">[Sid00]</a>.</p>
<table class="example">
<tr><td><pre>
gap> m := MealyMachine([[2,1],[3,2],[3,3]],[(),(1,2),()]);
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
gap> StateGrowth(m,Indeterminate(Rationals));
(-x_1+2)/(x_1^2-2*x_1+1)
gap> List(StateSet(m),i->Degree(FRElement(m,i)));
[ 2, 1, -1 ]
gap> a := MealyMachine(Group((1,2)),Group((1,2)),\*,\*);
<Mealy machine on alphabet [ (), (1,2) ] with states Group( [ (1,2) ] )>
gap> Degree(a);
infinity
</pre></td></tr></table>
<p><a id="X793C427084F830CE" name="X793C427084F830CE"></a></p>
<h5>5.2-10 IsFinitaryFRElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsFinitaryFRElement</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">> IsFinitaryFRMachine</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 finitary element.</p>
<p>This function tests whether <var class="Arg">e</var> is a finitary element. These are by definition the elements of growth degree at most 0.</p>
<p>When applied to a Mealy machine, it returns <code class="keyw">true</code> if all states of <var class="Arg">e</var> are finitary.</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->IsFinitaryFRElement(FRElement(m,i)));
[ 1, 2, 3 ]
gap> IsFinitaryFRElement(m);
false
</pre></td></tr></table>
<p><a id="X7E5E8B2C79688DC0" name="X7E5E8B2C79688DC0"></a></p>
<h5>5.2-11 Depth</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Depth</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">> DepthOfFRMachine</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">> DepthOfFRElement</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The depth of the finitary Mealy machine or element <var class="Arg">m</var>.</p>
<p>This function computes the maximal level at which the <var class="Arg">m</var> has an non-trivial state. In particular the identity has depth 0, and FR elements acting only at the root vertex have depth 1. The value <code class="keyw">infinity</code> is returned if <var class="Arg">m</var> is not finitary (see <code class="func">IsFinitaryFRElement</code> (<a href="chap5.html#X793C427084F830CE"><b>5.2-10</b></a>)).</p>
<table class="example">
<tr><td><pre>
gap> m := MealyMachine([[2,1],[3,3],[4,4],[4,4]],[(),(),(1,2),()]);
<Mealy machine on alphabet [ 1, 2 ] with 4 states>
gap> DepthOfFRMachine(m);
infinity
gap> List(StateSet(m),i->DepthOfFRElement(FRElement(m,i)));
[ infinity, 2, 1, 0 ]
</pre></td></tr></table>
<p><a id="X82F4410E85C54C7E" name="X82F4410E85C54C7E"></a></p>
<h5>5.2-12 IsBoundedFRElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsBoundedFRElement</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">> IsBoundedFRMachine</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 finitary element.</p>
<p>This function tests whether <var class="Arg">e</var> is a bounded element. These are by definition the elements of growth degree at most 1.</p>
<p>When applied to a Mealy machine, it returns <code class="keyw">true</code> if all states of <var class="Arg">e</var> are bounded.</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->IsBoundedFRElement(FRElement(m,i)));
[ 1, 2, 3, 4 ]
gap> IsBoundedFRMachine(m);
true
</pre></td></tr></table>
<p><a id="X81D4A3F27C5FAD96" name="X81D4A3F27C5FAD96"></a></p>
<h5>5.2-13 IsPolynomialGrowthFRElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsPolynomialGrowthFRElement</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">> IsPolynomialGrowthFRMachine</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 an element of polynomial growth.</p>
<p>This function tests whether <var class="Arg">e</var> is a polynomial element. These are by definition the elements of polynomial growth degree.</p>
<p>When applied to a Mealy machine, it returns <code class="keyw">true</code> if all states of <var class="Arg">e</var> are of polynomial growth.</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->IsPolynomialGrowthFRElement(FRElement(m,i)));
[ 1, 2, 3, 4 ]
gap> IsPolynomialGrowthFRMachine(m);
true
</pre></td></tr></table>
<p><a id="X7ECE17387910C023" name="X7ECE17387910C023"></a></p>
<h5>5.2-14 Signatures</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Signatures</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A list describing the product of the activities on each level.</p>
<p>This function computes the product of the activities of <var class="Arg">e</var> on each level, and returns a periodic list describing it (see <code class="func">PeriodicList</code> (<a href="chap12.html#X7B401DFE817D3927"><b>12.1-6</b></a>)).</p>
<p>The entries <code class="code">pi</code> are permutations, and their values are meaningful only when projected in the abelianization of <code class="code">VertexTransformationsFRElement(e)</code>.</p>
<table class="example">
<tr><td><pre>
gap> Signatures(GrigorchukGroup.1);
[ (1,2), / () ]
gap> Signatures(GrigorchukGroup.2);
[/ (), (1,2), (1,2) ]
gap> last[50];
(1,2)
gap> Signatures(AddingMachine(3)[2]);
[/ (1,2,3) ]
</pre></td></tr></table>
<p><a id="X83DFDC3384EA4634" name="X83DFDC3384EA4634"></a></p>
<h5>5.2-15 VertexTransformationsFRMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> VertexTransformationsFRMachine</code>( <var class="Arg">m</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">> VertexTransformationsFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The group/monoid generated by all vertex transformations of states of <var class="Arg">m</var>.</p>
<p>The first function computes the finite permutation group / transformation monoid generated by all outputs of states of <var class="Arg">m</var>.</p>
<p>The second command is a short-hand for <code class="code">VertexTransformationsFRMachine(UnderlyingFRMachine(e))</code>.</p>
<table class="example">
<tr><td><pre>
gap> m := MealyMachine([[1,3,2],[3,2,1],[2,1,3]],[(2,3),(1,3),(1,2)]);
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
gap> VertexTransformationsFRMachine(m);
Group([ (2,3), (1,3), (1,2) ])
</pre></td></tr></table>
<p><a id="X7E0CB3767CE08692" name="X7E0CB3767CE08692"></a></p>
<h5>5.2-16 FixedRay</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> FixedRay</code>( <var class="Arg">e</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>The lexicographically first ray fixed by <var class="Arg">e</var>.</p>
<p>This function computes the lexicographically first infinite sequence that is fixed by the FR element <var class="Arg">e</var>, and returns it as a periodic list (see <code class="func">PeriodicList</code> (<a href="chap12.html#X7B401DFE817D3927"><b>12.1-6</b></a>)). It returns <code class="keyw">fail</code> if no such ray exists.</p>
<table class="example">
<tr><td><pre>
gap> m := MealyMachine([[1,3,2],[3,2,1],[2,1,3]],[(2,3),(1,3),(1,2)]);
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
gap> FixedRay(FRElement(m,1));
[/ 1 ]
gap> last^FRElement(m,1);
[/ 1 ]
gap> FixedRay(FRElement(m,[1,2]));
fail
</pre></td></tr></table>
<p><a id="X828C167B7D7691E9" name="X828C167B7D7691E9"></a></p>
<h5>5.2-17 IsLevelTransitive</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> IsLevelTransitive</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> acts transitively on each level of the tree.</p>
<p>This function tests whether <var class="Arg">e</var> acts transitively on each level of the tree. It is implemented only if <code class="code">VertexTransformationsFRElement(e)</code> is abelian.</p>
<p>This function is used as a simple test to detect whether an element has infinite order: if <var class="Arg">e</var> has a fixed vertex v such that the <code class="code">State(e,v)</code> is level-transitive, then <var class="Arg">e</var> has infinite order.</p>
<table class="example">
<tr><td><pre>
gap> m := AddingMachine(3);; Display(m);
| 1 2 3
---+-----+-----+-----+
a | a,1 a,2 a,3
b | a,2 a,3 b,1
---+-----+-----+-----+
Initial state: b
gap> IsLevelTransitive(m);
true
gap> IsLevelTransitive(Product(UnderlyingFRMachine(GrigorchukOverGroup){[2..5]}));
true
</pre></td></tr></table>
<p><a id="X79EFE2C97D2CCEEC" name="X79EFE2C97D2CCEEC"></a></p>
<h5>5.2-18 AsMealyMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsMealyMachine</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A Mealy machine isomorphic to <var class="Arg">m</var>.</p>
<p>This function constructs a Mealy machine <code class="code">r</code>, which is as close as possible to the FR machine <var class="Arg">m</var>. Furthermore, <code class="code">Correspondence(r)</code> is a list identifying, for every generator of the stateset of <var class="Arg">m</var>, a corresponding state in the new Mealy machine; see <code class="func">Correspondence</code> (<a href="chap3.html#X7C107A42815F91DA"><b>3.5-11</b></a>).</p>
<p><var class="Arg">m</var> may be a group/monoid/semigroup FR machine, or a Mealy machine; in which case the result is returned unchanged.</p>
<p>In particular, <code class="code">FRElement(m,s)</code> and <code class="code">FRElement(AsMealyMachine(m),s)</code> return the same tree automorphism, for any FR machine <code class="code">m</code> and any state <code class="code">s</code>.</p>
<p>This function is not guaranteed to return; if <var class="Arg">m</var> does not have finite states, then it will loop forever.</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> Display(n);
| 1 2
-----+--------+---------+
tau | <id>,2 tau,1
mu | <id>,2 mu^-1,1
-----+--------+---------+
gap> AsMealyMachine(n);
<Mealy machine on alphabet [ 1, 2 ] with 4 states>
gap> Display(last);
| 1 2
---+-----+-----+
a | c,2 a,1
b | c,2 d,1
c | c,1 c,2
d | b,2 c,1
---+-----+-----+
gap> Correspondence(last);
[ 1, 2 ]
</pre></td></tr></table>
<p><a id="X80F9A18483F98442" name="X80F9A18483F98442"></a></p>
<h5>5.2-19 AsMealyMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsMealyMachine</code>( <var class="Arg">l</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A Mealy machine constructed out of the FR elements in <var class="Arg">l</var>.</p>
<p>This function constructs a Mealy machine <code class="code">r</code>, with states <var class="Arg">l</var> (which must be a state-closed set). Its outputs are the outputs of its elements, and its transitions are the transitions of its elements; in particular, <code class="code">FRElement(r,i)</code> is equal to <code class="code">l[i]</code> as an FR element.</p>
<p><code class="code">Correspondence(r)</code> records the argument <var class="Arg">l</var>.</p>
<p>This function returns <code class="keyw">fail</code> if <var class="Arg">l</var> is not state-closed.</p>
<table class="example">
<tr><td><pre>
gap> mu := FRElement([[[],[-1]]],[(1,2)],[1]);
<2|f1>
gap>
gap> States(mu);
[ <2|f1>, <2|identity ...>, <2|f1^-1> ]
gap> AsMealyMachine(last);
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
gap> Display(last);
| 1 2
---+-----+-----+
a | b,2 c,1
b | b,1 b,2
c | a,2 b,1
---+-----+-----+
</pre></td></tr></table>
<p><a id="X7FB3F0A2878DD2CF" name="X7FB3F0A2878DD2CF"></a></p>
<h5>5.2-20 AsMealyElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsMealyElement</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A Mealy element isomorphic to <var class="Arg">m</var>.</p>
<p>This function constructs a Mealy element, which induces the same tree automorphism as the FR element <var class="Arg">m</var>.</p>
<p><var class="Arg">m</var> may be a group/monoid/semigroup FR element, or a Mealy element; in which case the result is returned unchanged.</p>
<p>This function is not guaranteed to return; if <var class="Arg">m</var> does not have finite states, then it will loop forever.</p>
<table class="example">
<tr><td><pre>
gap> mu := FRElement([[[],[-1]]],[(1,2)],[1]);
<2|f1>
gap> AsMealyElement(mu);
<Mealy machine on alphabet [ 1, 2 ] with 3 states, initial state 1>
gap> [[2,1]]^last;
[ [ 1, 2 ] ]
gap> [2,1,2,1]^mu;
[ 1, 2, 1, 2 ]
</pre></td></tr></table>
<p><a id="X7FBBBD9A839011C8" name="X7FBBBD9A839011C8"></a></p>
<h5>5.2-21 AsIntMealyMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> AsIntMealyMachine</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">> AsIntMealyElement</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A Mealy machine in integer format, isomorphic to <var class="Arg">m</var>.</p>
<p>This function constructs a Mealy machine <code class="code">r</code>, which has similar behaviour as <var class="Arg">m</var> while having stateset <code class="code">[1..n]</code> for some natural <code class="code">n</code>. Most <strong class="pkg">FR</strong> commands operate efficiently only on Mealy machines of this type.</p>
<p>This function is not guaranteed to return; if <var class="Arg">m</var> does not have finite states, then it will loop forever.</p>
<table class="example">
<tr><td><pre>
gap> g := Group((1,2));; n := MealyMachine(g,g,\*,\*);
<Mealy machine on alphabet [ (), (1,2) ] with states Group( [ (1,2) ] )>
gap> Display(n);
| () (1,2)
-------+-------------+-------------+
() | (),() (1,2),(1,2)
(1,2) | (1,2),(1,2) (),()
-------+-------------+-------------+
gap> AsIntMealyMachine(n);
<Mealy machine on alphabet [ 1, 2 ] with 2 states>
gap> Display(last);
| 1 2
---+-----+-----+
a | a,1 b,2
b | b,2 a,1
---+-----+-----+
gap> Correspondence(last);
[ 1, 2 ]
</pre></td></tr></table>
<p><a id="X8191456B7E586785" name="X8191456B7E586785"></a></p>
<h5>5.2-22 TopElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> TopElement</code>( <var class="Arg">p[, n]</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A Mealy machine in integer format, acting on the first symbol of sequences.</p>
<p>This function constructs a Mealy machine <code class="code">r</code>, which acts as <var class="Arg">p</var> on the first letter of sequences and fixes the other letters. The argument <var class="Arg">n</var> is the size of the alphabet of <code class="code">r</code>; if it is ommitted, then it is assumed to be the degree of the transformation <var class="Arg">p</var>, or the largest moved point of the permutation or trans <var class="Arg">p</var>.</p>
<table class="example">
<tr><td><pre>
gap> a := TopElement((1,2));
<Mealy element on alphabet [ 1, 2 ] with 2 states>
gap> last=GrigorchukGroup.1;
true
gap> a := TopElement((1,2),3);
<Mealy element on alphabet [ 1, 2, 3 ] with 2 states>
gap> last in GuptaSidkiGroup;
false
</pre></td></tr></table>
<p><a id="X7A87ED9D789245E4" name="X7A87ED9D789245E4"></a></p>
<h5>5.2-23 ConfinalityClasses</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> ConfinalityClasses</code>( <var class="Arg">e</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">> IsWeaklyFinitaryFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>A list describing the non-trivial confinality classes of <var class="Arg">e</var>.</p>
<p>If <var class="Arg">e</var> is a bounded element (see <code class="func">IsBoundedFRElement</code> (<a href="chap5.html#X82F4410E85C54C7E"><b>5.2-12</b></a>)), there are finitely many infinite sequences that have confinality class larger that one; i.e. ultimately periodic sequences that are mapped by <var class="Arg">e</var> to a sequence with different period. This function returns a list of equivalence classes of periodic lists, see <code class="func">PeriodicList</code> (<a href="chap12.html#X7B401DFE817D3927"><b>12.1-6</b></a>), which are related under <var class="Arg">e</var>.</p>
<p>By definition, an element is <em>weakly finitary</em> if it has no non-singleton confinality classes.</p>
<table class="example">
<tr><td><pre>
gap> g := FRGroup("t=<,,t>(2,3)","u=<u,,>(1,2)","v=<u,t,>");;
gap> ConfinalityClasses(g.1);
[ {PeriodicList([ ],[ 2 ])} ]
gap> List(GeneratorsOfGroup(g),x->Elements(ConfinalityClasses(x)[1]));
[ [ [/ 2 ], [/ 3 ] ],
[ [/ 1 ], [/ 2 ] ],
[ [/ 1 ], [/ 2 ], [/ 3 ] ] ]
gap> IsWeaklyFinitaryFRElement(BinaryAddingElement);
false
gap> IsWeaklyFinitaryFRElement(GuptaSidkiGroup.2);
true
</pre></td></tr></table>
<p><a id="X81592E3D79745A40" name="X81592E3D79745A40"></a></p>
<h5>5.2-24 Germs</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> Germs</code>( <var class="Arg">e</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">> NormOfBoundedFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The germs of the bounded element <var class="Arg">e</var>.</p>
<p>The <em>germs</em> of a bounded element are the finitely many ultimately periodic sequences on which the state of <var class="Arg">e</var> does not vanish. This function returns the germs of <var class="Arg">e</var>, as a list of pairs; the first entry is a ray described as a periodic sequence of integers (see <code class="func">PeriodicList</code> (<a href="chap12.html#X7B401DFE817D3927"><b>12.1-6</b></a>)), and the second entry is the periodic sequence of states that appear along that ray.</p>
<p>The <em>norm</em> of a bounded element is the length of its list of germs.</p>
<table class="example">
<tr><td><pre>
gap> Germs(BinaryAddingElement);
[ [ [/ 2 ], [/ 1 ] ] ]
gap> Germs(GrigorchukGroup.1);
[ ]
gap> Germs(GrigorchukGroup.2);
[ [ [/ 2 ], [/ 1, 3, 5 ] ] ]
gap> Display(GrigorchukGroup.2);
| 1 2
---+-----+-----+
a | b,1 c,2
b | d,2 d,1
c | b,1 e,2
d | d,1 d,2
e | d,1 a,2
---+-----+-----+
Initial state: a
</pre></td></tr></table>
<p><a id="X7F76AF2D7C0279F9" name="X7F76AF2D7C0279F9"></a></p>
<h5>5.2-25 HasOpenSetConditionFRElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> HasOpenSetConditionFRElement</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> has the open set condition.</p>
<p>An FR element <var class="Arg">e</var> has the <em>open set condition</em> if for every infinite ray in the tree which is fixed by <var class="Arg">e</var>, there is an open set around that ray which is also fixed by <var class="Arg">e</var>. This function tests for <var class="Arg">e</var> to have the open set condition. It currently is implemented only for bounded elements.</p>
<table class="example">
<tr><td><pre>
gap> HasOpenSetConditionFRElement(GrigorchukGroup.1);
true
gap> HasOpenSetConditionFRElement(GrigorchukGroup.2);
false
</pre></td></tr></table>
<p><a id="X82308064814FEA51" name="X82308064814FEA51"></a></p>
<h5>5.2-26 LimitMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> LimitMachine</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The submachine of <var class="Arg">m</var> on all recurrent states.</p>
<p>This command creates a new Mealy machine, with stateset the limit states of <var class="Arg">m</var>.</p>
<table class="example">
<tr><td><pre>
gap> m := MealyMachine([[2,2,3],[2,3,3],[3,3,3]],[(),(),(1,2,3)]);
<Mealy machine on alphabet [ 1 .. 3 ] with 3 states>
gap> Display(m);
| 1 2 3
---+-----+-----+-----+
a | b,1 b,2 c,3
b | b,1 c,2 c,3
c | c,2 c,3 c,1
---+-----+-----+-----+
gap> LimitStates(m);
[ <Mealy element on alphabet [ 1 .. 3 ] with 2 states>,
<Mealy element on alphabet [ 1 .. 3 ] with 1 state> ]
gap> LimitMachine(m);
<Mealy machine on alphabet [ 1 .. 3 ] with 2 states>
gap> Display(last);
| 1 2 3
---+-----+-----+-----+
a | a,1 b,2 b,3
b | b,2 b,3 b,1
---+-----+-----+-----+
</pre></td></tr></table>
<p><a id="X7F8163B5816969C8" name="X7F8163B5816969C8"></a></p>
<h5>5.2-27 NucleusMachine</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> NucleusMachine</code>( <var class="Arg">m</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p><b>Returns: </b>The nucleus of <var class="Arg">m</var>.</p>
<p>This command creates a new Mealy machine <code class="code">n</code>, which is such that <code class="code">LimitMachine(m*n)</code> is isomorphic to <code class="code">n</code>, after minimisation. It is also isomorphic to the <code class="func">NucleusMachine</code> (<a href="chap7.html#X8443D711796F06E4"><b>7.2-18</b></a>) of the state closure of the <code class="func">SCSemigroup</code> (<a href="chap7.html#X853E3F0680C76F56"><b>7.1-2</b></a>) of <var class="Arg">m</var>. (Note that the ordering of the states in the resulting machine is not necessarily the same as in <var class="Arg">m</var>; however, if <var class="Arg">m</var> and <code class="code">n</code> are isomorphic, then this command returns <var class="Arg">m</var>).</p>
<table class="example">
<tr><td><pre>
gap> m := MealyMachine([[2,1,1],[2,2,2]],[(1,2,3),()]);
<Mealy machine on alphabet [ 1, 2, 3 ] with 2 states>
gap> Display(m);
| 1 2 3
---+-----+-----+-----+
a | b,2 a,3 a,1
b | b,1 b,2 b,3
---+-----+-----+-----+
gap> NucleusMachine(m);
<Mealy machine on alphabet [ 1, 2, 3 ] with 3 states>
gap> Display(last);
| 1 2 3
---+-----+-----+-----+
a | a,1 a,2 a,3
b | c,3 b,1 c,2
c | a,2 c,3 c,1
---+-----+-----+-----+
</pre></td></tr></table>
<p><a id="X7B29565784A591EC" name="X7B29565784A591EC"></a></p>
<h5>5.2-28 GuessMealyElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">> GuessMealyElement</code>( <var class="Arg">p, d, n</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p><b>Returns: </b>A Mealy element that probably has the same activity as <var class="Arg">p</var>.</p>
<p>This function receives a permutation or transformation <var class="Arg">p</var>, a degree <var class="Arg">d</var> and a level <var class="Arg">n</var>, and attempts to find a Mealy element on the alphabet <code class="code">[1..d]</code> whose activity on level <var class="Arg">n</var> is <var class="Arg">p</var>.</p>
<p>This function returns <code class="code">fail</code> if it thinks that the given level is not large enough to make a reasonable guess. In all cases, the function is not guaranteed to return the correct Mealy machine.</p>
<table class="example">
<tr><td><pre>
gap> GuessMealyElement(Activity(GrigorchukGroup.2,6),2,6);
<Mealy element on alphabet [ 1, 2 ] with 5 states>
gap> last=GrigorchukGroup.2;
true
gap> GuessMealyElement(Activity(GrigorchukGroup.2,5),2,5);
fail
gap> ComposeElement([GrigorchukGroup.2,One(GrigorchukGroup)],());
<Mealy element on alphabet [ 1, 2 ] with 6 states>
gap> last=GuessMealyElement(Activity(GrigorchukGroup.2,6),2,7);
true
</pre></td></tr></table>
<div class="chlinkprevnextbot"> <a href="chap0.html">Top of Book</a> <a href="chap4.html">Previous Chapter</a> <a href="chap6.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
>
1162
