|
|
|
|
Quelle chap5_mj.html
Sprache: HTML
|
|
| products/Sources/formale Sprachen/GAP/pkg/fr/doc/chap5_mj.html |
 |
<?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>
<script type="text/javascript"
src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<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" />
<script src="manual.js" type="text/javascript"></script>
<script type="text/javascript">overwriteStyle();</script>
</head>
<body class="chap5" onload="jscontent()">
<div class="chlinktop"><span class="chlink1">Goto Chapter: </span><a href="chap0_mj.html">Top</a> <a href="chap1_mj.html">1</a> <a href="chap2_mj.html">2</a> <a href="chap3_mj.html">3</a> <a href="chap4_mj.html">4</a> <a href="chap5_mj.html">5</a> <a href="chap6_mj.html">6</a> <a href="chap7_mj.html">7</a> <a href="chap8_mj.html">8</a> <a href="chap9_mj.html">9</a> <a href="chap10_mj.html">10</a> <a href="chap11_mj.html">11</a> <a href="chapBib_mj.html">Bib</a> <a href="chapInd_mj.html">Ind</a> </div>
<div class="chlinkprevnexttop"> <a href="chap0_mj.html">[Top of Book]</a> <a href="chap0_mj.html#contents">[Contents]</a> <a href="chap4_mj.html">[Previous Chapter]</a> <a href="chap6_mj.html">[Next Chapter]</a> </div>
<p id="mathjaxlink" class="pcenter"><a href="chap5.html">[MathJax off]</a></p>
<p><a id="X7C77EBC17DEF4CF6" name="X7C77EBC17DEF4CF6"></a></p>
<div class="ChapSects"><a href="chap5_mj.html#X7C77EBC17DEF4CF6">5 <span class="Heading">Mealy machines and elements</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.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>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7EF3E00080624B70">5.1-1 MealyMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X875B8FED7FD20FA1">5.1-2 MealyMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X8578657C7F4B6254">5.1-3 MealyMachineNC</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X83BBE01884D6E315">5.1-4 AllMealyMachines</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap5_mj.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>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7DF9F3AD86602DFC">5.2-1 Draw</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X8395542D846FA2B9">5.2-2 Minimized</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X809F069B798ED985">5.2-3 DualMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7D5D480C782FCC0B">5.2-4 IsReversible</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X8310A1C08158793C">5.2-5 IsMinimized</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7CCB79B981912CCC">5.2-6 AlphabetInvolution</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X80D2545D7D0990A2">5.2-7 IsBireversible</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X83364DAB825D7A0D">5.2-8 StateGrowth</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X84BE780A81CAC69C">5.2-9 Degree</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X793C427084F830CE">5.2-10 IsFinitaryFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7E5E8B2C79688DC0">5.2-11 Depth</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X82F4410E85C54C7E">5.2-12 IsBoundedFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X81D4A3F27C5FAD96">5.2-13 IsPolynomialGrowthFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7ECE17387910C023">5.2-14 Signatures</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X83DFDC3384EA4634">5.2-15 VertexTransformationsFRMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7E0CB3767CE08692">5.2-16 FixedRay</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7A519D4C86CC4786">5.2-17 IsLevelTransitiveFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X79EFE2C97D2CCEEC">5.2-18 AsMealyMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X80F9A18483F98442">5.2-19 AsMealyMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7FB3F0A2878DD2CF">5.2-20 AsMealyElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7FBBBD9A839011C8">5.2-21 AsIntMealyMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X8191456B7E586785">5.2-22 TopElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7A87ED9D789245E4">5.2-23 ConfinalityClasses</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X81592E3D79745A40">5.2-24 Germs</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7F76AF2D7C0279F9">5.2-25 HasOpenSetConditionFRElement</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X795017598575FCA3">5.2-26 LimitFRMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7F8163B5816969C8">5.2-27 NucleusMachine</a></span>
<span class="ContSS"><br /><span class="nocss"> </span><a href="chap5_mj.html#X7B29565784A591EC">5.2-28 GuessMealyElement</a></span>
</div></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_mj.html#X79EFE2C97D2CCEEC"><span class="RefLink">5.2-18</span></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 <span class="SimpleMath">\(m \times n\)</span> matrix, and the outputs are stored in a list of length <span class="SimpleMath">\(m\)</span>, 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="chap11_mj.html#X7B401DFE817D3927"><span class="RefLink">11.2-2</span></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_mj.html#X7EB36FBB78F4F26A"><span class="RefLink">3.2</span></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>Sometimes one would like to know how a Mealy element was obtained as a word in Mealy elements. This is possible within the representation <code class="func">IsFRMealyElement</code> (<a href="chap10_mj.html#X847A4BBE82C736B6"><span class="RefLink">10.2-12</span></a>), which combines the representations <code class="func">IsMealyElement</code> (<a href="chap10_mj.html#X7C86614187606A4C"><span class="RefLink">10.2-4</span></a>) and <code class="func">IsFRElement</code> (<a href="chap10_mj.html#X7966F9B982B1DFE1"><span class="RefLink">10.2-11</span></a>). On top of usual FR elements, they have an attribute <code class="code">UnderlyingMealyMachine</code>, which is used for faster comparison of elements, and computation of the action.</p>
<p>Therefore, if <code class="code">L</code> is a list of FR elements, the call <code class="code">List(L,UnderlyingElement);;</code> will set these attributes, and all calculations made with elements of <code class="code">L</code> will use and propagate the attributes. FR-Mealy elements are displayed in the form <code class="code"><d|w|n></code>, where <code class="code">d</code> is the degree of the alphabet, <code class="code">w</code> is a word in the stateset, and <code class="code">n</code> is the number of states of the underlying Mealy element.</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</var>, ]<var class="Arg">transitions</var>, <var class="Arg">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</var>, ]<var class="Arg">transitions</var>, <var class="Arg">output</var>, <var class="Arg">init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: 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 "[s]" 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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);</span>
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(b);</span>
| 1 2
---+-----+-----+
a | c,2 b,1
b | c,1 a,2
c | c,1 c,2
---+-----+-----+
<span class="GAPprompt">gap></span> <span class="GAPinput">n := MealyMachine(Domain([11,12]),[[3,2],[3,1],[3,3]],[(1,2),(),()]);</span>
<Mealy machine on alphabet [ 11, 12 ] with states [ 1 .. 3 ]>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(n);</span>
| 11 12
---+------+------+
a | c,12 b,11
b | c,11 a,12
c | c,11 c,12
---+------+------+
</pre></div>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">tau := MealyElement([[2,1],[2,2]],[(1,2),()],1);</span>
<Mealy machine on alphabet [ 1, 2 ] with 2 states, initial state 1>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(tau);</span>
| 1 2
---+-----+-----+
a | b,2 a,1
b | b,1 b,2
---+-----+-----+
Initial state: a
<span class="GAPprompt">gap></span> <span class="GAPinput">[1,1]^tau; [[1]]^tau; [[2]]^tau;</span>
[ 2, 1 ]
[ 2, [ 1 ] ]
[ [ 1 ] ]
</pre></div>
<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</var>, <var class="Arg">alphabet</var>, <var class="Arg">transitions</var>, <var class="Arg">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</var>, <var class="Arg">alphabet</var>, <var class="Arg">transitions</var>, <var class="Arg">output</var>, <var class="Arg">init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: 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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := Group((1,2));; n := MealyMachine(g,g,\*,\*);</span>
<Mealy machine on alphabet [ (), (1,2) ] with states Group( [ (1,2) ] )>
<span class="GAPprompt">gap></span> <span class="GAPinput">[(1,2),()]^FRElement(n,());</span>
[ (1,2), (1,2) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">a := MealyElement(g,g,\*,\*,());</span>
<Mealy machine on alphabet [ (), (1,2) ] with states Group(
[ (1,2) ] ), initial state ()>
<span class="GAPprompt">gap></span> <span class="GAPinput">[(1,2),()]^a;</span>
[ (1,2), (1,2) ]
</pre></div>
<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</var>, <var class="Arg">transitions</var>, <var class="Arg">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</var>, <var class="Arg">transitions</var>, <var class="Arg">output</var>, <var class="Arg">init</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: 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><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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">taum := MealyMachine([[2,1],[2,2]],[(1,2),()]);</span>
<Mealy machine on alphabet [ 1, 2 ] with 2 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">tauminv := MealyMachineNC(FamilyObj(taum),[[1,2],[2,2]],[(1,2),()]);</span>
<Mealy machine on alphabet [ 1, 2 ] with 2 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">tau := MealyElement([[2,1],[2,2]],[(1,2),()],1);</span>
<Mealy machine on alphabet [ 1, 2 ] with 2 states, initial state 1>
<span class="GAPprompt">gap></span> <span class="GAPinput">tauinv := MealyElementNC(FamilyObj(n),[[1,2],[2,2]],[(1,2),()],1);</span>
<Mealy machine on alphabet [ 1, 2 ] with 2 states, initial state 1>
<span class="GAPprompt">gap></span> <span class="GAPinput">tau=FRElement(taum,1); tauinv=FRElement(tauminv,1);</span>
true
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsOne(tau*tauinv);</span>
true
</pre></div>
<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</var>, <var class="Arg">n</var>[, <var class="Arg">filters</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list of all Mealy machines with specified properties.</p>
<p>This function constructs all Mealy machines 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="chap10_mj.html#X83AEFB8184F4B023"><span class="RefLink">10.2-15</span></a>), <code class="func">IsReversible</code> (<a href="chap5_mj.html#X7D5D480C782FCC0B"><span class="RefLink">5.2-4</span></a>), <code class="func">IsBireversible</code> (<a href="chap5_mj.html#X80D2545D7D0990A2"><span class="RefLink">5.2-7</span></a>), and <code class="func">IsMinimized</code> (<a href="chap5_mj.html#X8310A1C08158793C"><span class="RefLink">5.2-5</span></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_mj.html#X83DFDC3384EA4634"><span class="RefLink">5.2-15</span></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 argument <code class="code">InverseClasses</code> returns one isomorphism class of Mealy machine under inversion of the stateset.</p>
<p>The following example constructs the two Mealy machines <code class="func">AleshinMachine</code> (<a href="chap9_mj.html#X7C286D3A84790ECE"><span class="RefLink">9.1-15</span></a>) and <code class="func">BabyAleshinMachine</code> (<a href="chap9_mj.html#X7E024B4D7BA411B1"><span class="RefLink">9.1-16</span></a>):</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">l := AllMealyMachines(2,3,IsBireversible,IsSurjective,EquivalenceClasses);;</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">Length(l);</span>
20
<span class="GAPprompt">gap></span> <span class="GAPinput">Filtered(l,x->VertexTransformationsFRMachine(DualMachine(x))=SymmetricGroup(3)</span>
<span class="GAPprompt">></span> <span class="GAPinput"> and Size(StateSet(Minimized(x)))=3);</span>
[ <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
---+-----+-----+
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last[2]);</span>
| 1 2
---+-----+-----+
a | a,2 b,1
b | c,1 c,2
c | b,2 a,1
---+-----+-----+
</pre></div>
<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</var>[, <var class="Arg">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> or <strong class="pkg">rsvg-view</strong>. This works on UNIX systems.</p>
<p>It is assumed, but not checked, that <strong class="pkg">graphviz</strong> and <strong class="pkg">display</strong>/<strong class="pkg">rsvg-view</strong> are properly installed on the system. The option <code class="keyw">usesvg</code> requests the use of <strong class="pkg">rsvg-view</strong>; by default, <strong class="pkg">display</strong> is used.</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 <span class="SimpleMath">\(x/y\)</span>, where <span class="SimpleMath">\(x\)</span> is the input symbol and <span class="SimpleMath">\(y\)</span> 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_mj.html#X79EFE2C97D2CCEEC"><span class="RefLink">5.2-18</span></a>)).</p>
<p>The optional value "detach" detaches the drawing subprocess after it is started, in the syntax <code class="code">Draw(M:detach)</code>.</p>
<p>It is assumed that <strong class="pkg">graphviz</strong> and <strong class="pkg">display</strong>/<strong class="pkg">rsvg-view</strong> are properly installed on the system. The option <code class="keyw">usesvg</code> requests the use of <strong class="pkg">rsvg-view</strong>; by default, <strong class="pkg">display</strong> is used.</p>
<p>For example, the command <code class="code">Draw(NucleusMachine(BasilicaGroup));</code> produces (in a new window) the following picture: <img alt="Nucleus" src="basilica-nucleus.jpg"></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>Returns: 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_mj.html#X7C107A42815F91DA"><span class="RefLink">3.5-12</span></a>).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">GrigorchukMachine := MealyMachine([[2,3],[4,4],[2,5],[4,4],[4,1]],</span>
[(),(1,2),(),(),()]);
<Mealy machine on alphabet [ 1, 2 ] with 5 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">g2 := GrigorchukMachine^2;</span>
<Mealy machine on alphabet [ 1, 2 ] with 25 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">Minimized(g2);</span>
<Mealy machine on alphabet [ 1, 2 ] with 11 states, minimized>
<span class="GAPprompt">gap></span> <span class="GAPinput">Correspondence(last);</span>
[ 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 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">e := FRElement(g2,11);</span>
<Mealy element on alphabet [ 1, 2 ] with 25 states, initial state 11>
<span class="GAPprompt">gap></span> <span class="GAPinput">Minimized(e);</span>
<Mealy element on alphabet [ 1, 2 ] with 5 states, initial state 1, minimized>
<span class="GAPprompt">gap></span> <span class="GAPinput">Correspondence(last);</span>
[ 3, 2, 1, 4, 5, 2, 3,,,, 1,, 3, 5, 4, 4,, 5, 3, 1, 5,, 4, 1, 3 ]
</pre></div>
<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>Returns: 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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);</span>
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">d := DualMachine(b)^4);</span>
<Mealy machine on alphabet [ 1, 2, 3 ] with 16 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">Draw(d); # action on 2^4 points</span>
<span class="GAPprompt">gap></span> <span class="GAPinput">DualMachine(d);</span>
<Mealy machine on alphabet [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
] with 3 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">Output(last,1)=Activity(FRElement(b,1),4);</span>
true
</pre></div>
<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>Returns: <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_mj.html#X809F069B798ED985"><span class="RefLink">5.2-3</span></a>) of <var class="Arg">m</var> is invertible. See <a href="chapBib_mj.html#biBMR1841119">[MNS00]</a> for more details.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsReversible(MealyMachine([[1,2],[2,2]],[(1,2),()]));</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsReversible(MealyMachine([[1,2],[2,1]],[(),(1,2)]));</span>
</pre></div>
<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>Returns: <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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">AllMealyMachines(2, 2, IsBireversible,EquivalenceClasses);</span>
[ <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> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">List(last,IsMinimized);</span>
[ false, true, false, false, false, false, true, false ]
</pre></div>
<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>Returns: 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_mj.html#X809F069B798ED985"><span class="RefLink">5.2-3</span></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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := GammaPQMachine(3,5);; AlphabetOfFRObject(m);</span>
[ 1 .. 6 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBireversible(m); AlphabetInvolution(GammaPQMachine(3,5));</span>
true
[ 6, 5, 4, 3, 2, 1 ]
</pre></div>
<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>Returns: <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_mj.html#X809F069B798ED985"><span class="RefLink">5.2-3</span></a>) and <code class="code">Inverse</code> are well-defined. See <a href="chapBib_mj.html#biBMR1841119">[MNS00]</a> for more details.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBireversible(MealyMachine([[1,2],[2,1]],[(),(1,2)]));</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBireversible(MealyMachine([[1,1],[2,2]],[(),(1,2)]));</span>
true
</pre></div>
<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</var>[, <var class="Arg">x</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>Returns: 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 <span class="SimpleMath">\(n\)</span> is the number of non-trivial states at level <span class="SimpleMath">\(n\)</span> 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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">b := MealyMachine([[3,2],[3,1],[3,3]],[(1,2),(),()]);</span>
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">StateGrowth(b,Indeterminate(Rationals));</span>
(2)/(-x_1+1)
<span class="GAPprompt">gap></span> <span class="GAPinput">StateGrowth(FRElement(b,1),Indeterminate(Rationals));</span>
(1)/(-x_1+1)
</pre></div>
<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>Returns: 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 <span class="SimpleMath">\(x=1\)</span> 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_mj.html#biBMR1774362">[Sid00]</a>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := MealyMachine([[2,1],[3,2],[3,3]],[(),(1,2),()]);</span>
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">StateGrowth(m,Indeterminate(Rationals));</span>
(-x_1+2)/(x_1^2-2*x_1+1)
<span class="GAPprompt">gap></span> <span class="GAPinput">List(StateSet(m),i->Degree(FRElement(m,i)));</span>
[ 2, 1, -1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">a := MealyMachine(Group((1,2)),Group((1,2)),\*,\*);</span>
<Mealy machine on alphabet [ (), (1,2) ] with states Group( [ (1,2) ] )>
<span class="GAPprompt">gap></span> <span class="GAPinput">Degree(a);</span>
infinity
</pre></div>
<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>Returns: <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 <span class="SimpleMath">\(0\)</span>.</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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := GuptaSidkiMachines(3);; Display(m);</span>
| 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
---+-----+-----+-----+
<span class="GAPprompt">gap></span> <span class="GAPinput">Filtered(StateSet(m),i->IsFinitaryFRElement(FRElement(m,i)));</span>
[ 1, 2, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsFinitaryFRElement(m);</span>
false
</pre></div>
<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>Returns: 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_mj.html#X793C427084F830CE"><span class="RefLink">5.2-10</span></a>)).</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := MealyMachine([[2,1],[3,3],[4,4],[4,4]],[(),(),(1,2),()]);</span>
<Mealy machine on alphabet [ 1, 2 ] with 4 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">DepthOfFRMachine(m);</span>
infinity
<span class="GAPprompt">gap></span> <span class="GAPinput">List(StateSet(m),i->DepthOfFRElement(FRElement(m,i)));</span>
[ infinity, 2, 1, 0 ]
</pre></div>
<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>Returns: <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 <span class="SimpleMath">\(1\)</span>.</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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := GuptaSidkiMachines(3);; Display(m);</span>
| 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
---+-----+-----+-----+
<span class="GAPprompt">gap></span> <span class="GAPinput">Filtered(StateSet(m),i->IsBoundedFRElement(FRElement(m,i)));</span>
[ 1, 2, 3, 4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsBoundedFRMachine(m);</span>
true
</pre></div>
<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>Returns: <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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := GuptaSidkiMachines(3);; Display(m);</span>
| 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
---+-----+-----+-----+
<span class="GAPprompt">gap></span> <span class="GAPinput">Filtered(StateSet(m),i->IsPolynomialGrowthFRElement(FRElement(m,i)));</span>
[ 1, 2, 3, 4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">IsPolynomialGrowthFRMachine(m);</span>
true
</pre></div>
<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>Returns: 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="chap11_mj.html#X7B401DFE817D3927"><span class="RefLink">11.2-2</span></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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Signatures(GrigorchukGroup.1);</span>
[ (1,2), / () ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Signatures(GrigorchukGroup.2);</span>
[/ (), (1,2), (1,2) ]
<span class="GAPprompt">gap></span> <span class="GAPinput">last[50];</span>
(1,2)
<span class="GAPprompt">gap></span> <span class="GAPinput">Signatures(AddingMachine(3)[2]);</span>
[/ (1,2,3) ]
</pre></div>
<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>Returns: 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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := MealyMachine([[1,3,2],[3,2,1],[2,1,3]],[(2,3),(1,3),(1,2)]);</span>
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">VertexTransformationsFRMachine(m);</span>
Group([ (2,3), (1,3), (1,2) ])
</pre></div>
<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>Returns: 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="chap11_mj.html#X7B401DFE817D3927"><span class="RefLink">11.2-2</span></a>)). It returns <code class="keyw">fail</code> if no such ray exists.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := MealyMachine([[1,3,2],[3,2,1],[2,1,3]],[(2,3),(1,3),(1,2)]);</span>
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">FixedRay(FRElement(m,1));</span>
[/ 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">last^FRElement(m,1);</span>
[/ 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">FixedRay(FRElement(m,[1,2]));</span>
fail
</pre></div>
<p><a id="X7A519D4C86CC4786" name="X7A519D4C86CC4786"></a></p>
<h5>5.2-17 IsLevelTransitiveFRElement</h5>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsLevelTransitiveFRElement</code>( <var class="Arg">e</var> )</td><td class="tdright">( property )</td></tr></table></div>
<p>Returns: <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 <span class="SimpleMath">\(v\)</span> such that the <code class="code">State(e,v)</code> is level-transitive, then <var class="Arg">e</var> has infinite order.</p>
<p>This function can be abbreviated as <code class="code">IsLevelTransitive</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">m := AddingMachine(3);; Display(m);</span>
| 1 2 3
---+-----+-----+-----+
a | a,1 a,2 a,3
b | a,2 a,3 b,1
---+-----+-----+-----+
Initial state: b
<span class="GAPprompt">gap></span> <span class="GAPinput">IsLevelTransitiveFRElement(m);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsLevelTransitiveFRElement(Product(UnderlyingFRMachine(GrigorchukOverGroup){[2..5]}));</span>
true
</pre></div>
<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>Returns: 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_mj.html#X7C107A42815F91DA"><span class="RefLink">3.5-12</span></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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">n := FRMachine(["tau","mu"],[[[],[1]],[[],[-2]]],[(1,2),(1,2)]);</span>
<FR machine with alphabet [ 1 .. 2 ] on Group( [ tau, mu ] )>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(n);</span>
| 1 2
-----+--------+---------+
tau | <id>,2 tau,1
mu | <id>,2 mu^-1,1
-----+--------+---------+
<span class="GAPprompt">gap></span> <span class="GAPinput">AsMealyMachine(n);</span>
<Mealy machine on alphabet [ 1, 2 ] with 4 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);</span>
| 1 2
---+-----+-----+
a | c,2 a,1
b | c,2 d,1
c | c,1 c,2
d | b,2 c,1
---+-----+-----+
<span class="GAPprompt">gap></span> <span class="GAPinput">Correspondence(last);</span>
[ 1, 2 ]
</pre></div>
<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>Returns: 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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput"> mu := FRElement([[[],[-1]]],[(1,2)],[1]);</span>
<2|f1>
gap>
<span class="GAPprompt">gap></span> <span class="GAPinput">States(mu);</span>
[ <2|f1>, <2|identity ...>, <2|f1^-1> ]
<span class="GAPprompt">gap></span> <span class="GAPinput">AsMealyMachine(last);</span>
<Mealy machine on alphabet [ 1, 2 ] with 3 states>
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);</span>
| 1 2
---+-----+-----+
a | b,2 c,1
b | b,1 b,2
c | a,2 b,1
---+-----+-----+
</pre></div>
<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>Returns: 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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">mu := FRElement([[[],[-1]]],[(1,2)],[1]);</span>
<2|f1>
<span class="GAPprompt">gap></span> <span class="GAPinput">AsMealyElement(mu);</span>
<Mealy machine on alphabet [ 1, 2 ] with 3 states, initial state 1>
<span class="GAPprompt">gap></span> <span class="GAPinput">[[2,1]]^last;</span>
[ [ 1, 2 ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">[2,1,2,1]^mu;</span>
[ 1, 2, 1, 2 ]
</pre></div>
<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>Returns: 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>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">g := Group((1,2));; n := MealyMachine(g,g,\*,\*);</ | | |
