Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/GAP/pkg/patternclass/doc/   (Algebra von RWTH Aachen Version 4.15.1©)  Datei vom 30.7.2024 mit Größe 13 kB image not shown  

Quelle  chap4.html   Sprache: HTML

 
 products/Sources/formale Sprachen/GAP/pkg/patternclass/doc/chap4.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>
<title>GAP (PatternClass) - Chapter 4: From Networks to Automata</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="chap4"  onload="jscontent()">


<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="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<div class="chlinkprevnexttop"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap3.html">[Previous Chapter]</a>    <a href="chap5.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap4_mj.html">[MathJax on]</a></p>
<p><a id="X84E9957A81BF938D" name="X84E9957A81BF938D"></a></p>
<div class="ChapSects"><a href="chap4.html#X84E9957A81BF938D">4 <span class="Heading">From Networks to Automata</span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap4.html#X86FA580F8055B274">4.1 <span class="Heading">Functions</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7CFD21C47E43D8FF">4.1-1 GraphToAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap4.html#X7D457B517F2FDDA9">4.1-2 ConstrainedGraphToAut</a></span>
</div></div>
</div>

<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>

<p><a id="X86FA580F8055B274" name="X86FA580F8055B274"></a></p>

<h4>4.1 <span class="Heading">Functions</span></h4>

<p><a id="X7CFD21C47E43D8FF" name="X7CFD21C47E43D8FF"></a></p>

<h5>4.1-1 GraphToAut</h5>

<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>


<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:=GraphToAut(x,1,6);</span>
< epsilon automaton on 4 letters with 64 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=MinimalAutomaton(aut);</span>
< deterministic automaton on 3 letters with 3 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(aut);</span>
   |  1  2  3  
--------------
 a |  1  3  1  
 b |  3  3  3  
 c |  2  2  2  
Initial state:   [ 1 ]
Accepting state: [ 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

<p>The minimal automaton corresponding to <code class="code">Seqstacks(2,2)</code> is: <br><center><img src="img/ss22aut.jpg" WIDTH=158 HEIGHT=243 ></center><br></p>


<div class="example"><pre>  
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=Parstacks(2,2);</span>
[ [ 2, 4 ], [ 3, 6 ], [ 2 ], [ 5, 6 ], [ 4 ], [  ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=GraphToAut(x,1,6);</span>
< epsilon automaton on 5 letters with 66 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=MinimalAutomaton(aut);</span>
< deterministic automaton on 4 letters with 9 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(aut);</span>
   |  1  2  3  4  5  6  7  8  9  
--------------------------------
 a |  1  2  1  3  2  2  6  6  3  
 b |  3  2  3  3  4  3  6  9  3  
 c |  9  2  9  4  6  6  4  9  9  
 d |  8  2  8  7  5  5  7  8  8  
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">Parstacks(2,2)</code> are accepted by the following automaton: <br><center><img src="img/ps22aut.jpg" WIDTH=537 HEIGHT=542 ></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:=GraphToAut(x,1,7);</span>
< epsilon automaton on 5 letters with 460 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=MinimalAutomaton(aut);</span>
< deterministic automaton on 4 letters with 4 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(aut);</span>
   |  1  2  3  4  
-----------------
 a |  1  4  1  3  
 b |  3  4  3  3  
 c |  4  4  4  4  
 d |  2  2  2  2  
Initial state:   [ 1 ]
Accepting state: [ 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

<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>


<div class="example"><pre>  
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=[[2,3],[4],[5],[3,6],[6],[]];</span>
[ [ 2, 3 ], [ 4 ], [ 5 ], [ 3, 6 ], [ 6 ], [  ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=GraphToAut(x,1,6);</span>
< epsilon automaton on 4 letters with 80 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=MinimalAutomaton(aut);</span>
< deterministic automaton on 3 letters with 8 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(aut);</span>
   |  1  2  3  4  5  6  7  8  
-----------------------------
 a |  1  3  1  4  6  1  6  1  
 b |  3  8  3  4  4  6  6  6  
 c |  2  2  2  4  5  5  7  7  
Initial state:   [ 1 ]
Accepting state: [ 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

<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>

<p><a id="X7D457B517F2FDDA9" name="X7D457B517F2FDDA9"></a></p>

<h5>4.1-2 ConstrainedGraphToAut</h5>

<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>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">x:=[[2,3],[4],[5],[3,6],[6],[]];                      </span>
[ [ 2, 3 ], [ 4 ], [ 5 ], [ 3, 6 ], [ 6 ], [  ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=ConstrainedGraphToAut(x,1,6,3);</span>
< epsilon automaton on 6 letters with 48 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=MinimalAutomaton(aut);         </span>
< deterministic automaton on 5 letters with 8 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(aut);                       </span>
   |  1  2  3  4  5  6  7  8  
-----------------------------
 a |  1  3  1  4  6  1  6  1  
 b |  3  8  3  4  4  6  6  6  
 c |  2  2  2  4  5  5  7  7  
 d |  4  4  4  4  4  4  4  4  
 e |  4  4  4  4  4  4  4  4  
Initial state:   [ 1 ]
Accepting state: [ 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

<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>


<div class="chlinkprevnextbot"> <a href="chap0.html">[Top of Book]</a>   <a href="chap0.html#contents">[Contents]</a>    <a href="chap3.html">[Previous Chapter]</a>    <a href="chap5.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><span class="chlink1">Goto Chapter: </span><a href="chap0.html">Top</a>  <a href="chap1.html">1</a>  <a href="chap2.html">2</a>  <a href="chap3.html">3</a>  <a href="chap4.html">4</a>  <a href="chap5.html">5</a>  <a href="chap6.html">6</a>  <a href="chap7.html">7</a>  <a href="chap8.html">8</a>  <a href="chap9.html">9</a>  <a href="chap10.html">10</a>  <a href="chapBib.html">Bib</a>  <a href="chapInd.html">Ind</a>  </div>

<hr />
<p class="foot">generated by <a href="https://www.math.rwth-aachen.de/~Frank.Luebeck/GAPDoc">GAPDoc2HTML</a></p>
</body>
</html>

100%


¤ Dauer der Verarbeitung: 0.15 Sekunden  (vorverarbeitet)  ¤

*© Formatika GbR, Deutschland




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

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.