<h3>4 <span class="Heading">From Networks to Automata</span></h3>
<p>It is known that the language of all encoded permutations of a TPN is rational, and thus is it indeed possible to turn a TPN into an automaton. The idea is to inspect all dispositions of tokens within the TPN and find equivalence classes of these dispositions, for more details consult <a href="chapBib.html#biBPermGenTPGraph">[ALTnd]</a>. Adding a constraint, which limits the number of tokens at any time within the TPN, is also considered in this chapter.</p>
<p>The algorithms featured in this chapter do not return the minimal automata representing the input TPN as they are exactly visualising the equivalence classes of the dispositions of the tokens in the TPN. The automaton can be minimalised by choice, as it simplifies future computations involving the automaton also is makes the automata more legible.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GraphToAut</code>( <var class="Arg">g</var>, <var class="Arg">innode</var>, <var class="Arg">outnode</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An automaton representing the input TPN.</p>
<p><code class="code">GraphToAut</code> turns an array represented directed graph, with a distinct input node and a distinct output node, into the corresponding automaton, that accepts the language build by the resulting rank encoded permutations of the directed graph.</p>
<p>The rank encoded permutations of <code class="code">Parstacks(2,2)</code> are accepted by the following automaton: <br><center><img src="img/ps22aut.jpg" WIDTH=537 HEIGHT=542 ></center><br></p>
<p>The following automaton represents the language of rank encoded permutations that are output by <code class="code">BufferAndStack(3,2)</code>: <br><center><img src="img/bs32aut.jpg" WIDTH=164 HEIGHT=381 ></center><br></p>
<p>The input TPN here is the first network described in Chapter <a href="chap2.html#X7C769071875E96B2"><span class="RefLink">2.</span></a>. The language of rank encoded permutations of this token passing network is accepted by the following automaton: <br><center><img src="img/hexaut.jpg"WIDTH=459 HEIGHT=346 ></center><br></p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ConstrainedGraphToAut</code>( <var class="Arg">g</var>, <var class="Arg">innode</var>, <var class="Arg">outnode</var>, <var class="Arg">capacity</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An automaton representing the input TPN with bounded capacity.</p>
<p><code class="code">ConstrainedGraphToAut</code> builds an epsilon automaton based on the same idea as <code class="code">GraphToAut</code>, so it takes a list representation of a directed graph, a designated input node and a distinct output node, but additionally there is the constraint that there can be at most <code class="code">capacity</code> tokens in the graph, at any time.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=Seqstacks(2,2); </span>
[ [ 2 ], [ 3, 4 ], [ 2 ], [ 5, 6 ], [ 4 ], [ ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=ConstrainedGraphToAut(x,1,6,2);</span>
< epsilon automaton on 6 letters with 21 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=MinimalAutomaton(aut); </span>
< deterministic automaton on 5 letters with 3 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(aut); </span>
| 1 2 3
--------------
a | 1 2 1
b | 3 2 3
c | 2 2 2
d | 2 2 2
e | 2 2 2
Initial state: [ 1 ]
Accepting state: [ 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>
<p>The rank encoded permutations of <code class="code">Seqstacks(2,2)</code>, where at any time there are at most 2 tokens within the network, are accepted by the following automaton: <br><center><img src="img/ss22c2aut.jpg" WIDTH=150 HEIGHT=289 ></center><br></p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=BufferAndStack(3,2); </span>
[ [ 2 .. 4 ], [ 5 ], [ 5 ], [ 5 ], [ 6, 7 ], [ 5 ], [ ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=ConstrainedGraphToAut(x,1,6,3);</span>
< epsilon automaton on 7 letters with 112 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=MinimalAutomaton(aut);</span>
< deterministic automaton on 6 letters with 4 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(aut);</span>
| 1 2 3 4
-----------------
a | 1 2 1 3
b | 3 2 3 3
c | 4 2 4 4
d | 2 2 2 2
e | 2 2 2 2
f | 2 2 2 2
Initial state: [ 1 ]
Accepting state: [ 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>
<p>The automaton corresponding to <code class="code">BufferAndStack(3,2)</code> with limited capacity of 3 tokens is: <br><center><img src="img/bs32c3aut.jpg" WIDTH=198 HEIGHT=421 ></center><br></p>
<p>The automaton that accepts the language of rank encoded permutations of the token passing network, from Chapter <a href="chap2.html#X7C769071875E96B2"><span class="RefLink">2.</span></a>, with at most 3 tokens in the network at anytime, is: <br><center><img src="img/hexc3aut.jpg" WIDTH=570 HEIGHT=440 ></center><br></p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
