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 32 kB image not shown  

Quelle  chap9_mj.html   Sprache: HTML

 
 products/sources/formale Sprachen/GAP/pkg/patternclass/doc/chap9_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 (PatternClass) - Chapter 9:  Regular Languages of Sets of Permutations </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="chap9"  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="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="chap8_mj.html">[Previous Chapter]</a>    <a href="chap10_mj.html">[Next Chapter]</a>   </div>

<p id="mathjaxlink" class="pcenter"><a href="chap9.html">[MathJax off]</a></p>
<p><a id="X7E9C84807FCB6408" name="X7E9C84807FCB6408"></a></p>
<div class="ChapSects"><a href="chap9_mj.html#X7E9C84807FCB6408">9 <span class="Heading"> Regular Languages of Sets of Permutations </span></a>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9_mj.html#X82F103DB7A446E7B">9.1 <span class="Heading"> Inversions in Permutations </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X79B3989A7D90B227">9.1-1 InversionAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7C6166407D4A1798">9.1-2 InversionAutOfClass</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9_mj.html#X8603B5A3872690FD">9.2 <span class="Heading"> Plus- and Minus-(In)Decomposablilty </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7B43561F78C4C03C">9.2-1 PlusDecomposableAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X780030727DF57B1C">9.2-2 PlusIndecomposableAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X80F5A8AC8306FEE2">9.2-3 MinusDecomposableAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X8689DB147A7EE2C1">9.2-4 MinusIndecomposableAut</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9_mj.html#X80E741077DE09F63">9.3 <span class="Heading"> Language of all non-simple permutations </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7EE214F57A6350E0">9.3-1 LengthBoundAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7B11C3137DEA8B4B">9.3-2 ShiftAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X864D53717A30C8EE">9.3-3 NextGap</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7A660F527E913DB6">9.3-4 GapAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X809340BA7C999E86">9.3-5 SumAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X83BD683B7A92D492">9.3-6 GapSumAut</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X867C42167E943F94">9.3-7 NonSimpleAut</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9_mj.html#X7B82346E7E2C330C">9.4 <span class="Heading"> Simplicity </span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7C7F3B6680370860">9.4-1 SimplePermAut</a></span>
</div></div>
<div class="ContSect"><span class="tocline"><span class="nocss"> </span><a href="chap9_mj.html#X82CA692F808FA08F">9.5 <span class="Heading">Exceptionality</span></a>
</span>
<div class="ContSSBlock">
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X820901F881D220EE">9.5-1 IsExceptionalPerm</a></span>
<span class="ContSS"><br /><span class="nocss">  </span><a href="chap9_mj.html#X7B0086217E986ADA">9.5-2 ExceptionalBoundedAutomaton</a></span>
</div></div>
</div>

<h3>9 <span class="Heading"> Regular Languages of Sets of Permutations </span></h3>

<p>This chapter is dedicated to the different sets of permutations with the same properties.</p>

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

<h4>9.1 <span class="Heading"> Inversions in Permutations </span></h4>

<p>An inversion in a permutation <span class="SimpleMath">\(\tau=\tau_{1}\ldots\tau_{n}\)</span> is a pair <span class="SimpleMath">\((i,j)\)</span> such that <span class="SimpleMath">\(1\leq i<j\leq n\)</span> and <span class="SimpleMath">\(\tau_{i}>\tau_{j}\)</span> <a href="chapBib_mj.html#biBUpBndStanWilf1324">[CJS11]</a>.</p>

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

<h5>9.1-1 InversionAut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InversionAut</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An automaton that accepts all permutations with exactly <code class="code">k</code> inversions.</p>

<p>The rational language of all permutations with a given number , <code class="code">k</code>, of inversions is computed by <code class="code">InversionAut</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=InversionAut(1);</span>
< deterministic automaton on 2 letters with 4 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">AutToRatExp(a);</span>
a*baa*
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(a);     </span>
[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">b:=InversionAut(5);</span>
< deterministic automaton on 6 letters with 14 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">AutToRatExp(b);</span>
((a*ba*bUa*c)a*bUa*ba*cUa*d)a*(ba*baa*Ucaaa*)U(a*ba*bUa*c)a*(ca*baa*Udaaaa*)U(\
a*ba*daUa*eaa)a*baa*Ua*ba*(dbUeaa)aaa*U(a*eabUa*(ebUfaa)a)aaa*
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(b);   </span>
[ 0, 0, 0, 3, 22, 71, 169, 343, 628, 1068, 1717, 2640, 3914, 5629, 7889 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

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

<h5>9.1-2 InversionAutOfClass</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InversionAutOfClass</code>( <var class="Arg">aut</var>, <var class="Arg">inv</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An automaton accepting all permutations of a class with <code class="code">inv</code> inversions.</p>

<p><code class="code">InversionAutOfClass</code> intersects the rational pattern class with the rational language containing all permutations under the rank encoding that have exactly <code class="code">inv</code> inversions.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=MinimalAutomaton(GraphToAut(Seqstacks(2,2),1,6));</span>
< deterministic automaton on 3 letters with 3 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(a);                                        </span>
[ 1, 2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366, 118098, 354294, 
  1062882, 3188646 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">b:=InversionAutOfClass(a,4);                        </span>
< deterministic automaton on 5 letters with 23 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(b);                                        </span>
[ 0, 0, 0, 3, 13, 35, 75, 140, 238, 378, 570, 825, 1155, 1573, 2093 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

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

<h4>9.2 <span class="Heading"> Plus- and Minus-(In)Decomposablilty </span></h4>

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

<h5>9.2-1 PlusDecomposableAut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PlusDecomposableAut</code>( <var class="Arg">aut</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An automaton that accepts the subset of the class <code class="code">aut</code> containing the plus-decomposable permutations of <code class="code">aut</code>.</p>

<p>The <code class="code">PlusDecomposableAut</code> automaton accepts the language of all plus-decomposable permutations of the encoded class accepted by <code class="code">aut</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">xa:=MinimalAutomaton(GraphToAut(Parstacks(2,2),1,6));</span>
< deterministic automaton on 4 letters with 9 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(xa);</span>
[ 1, 2, 6, 23, 89, 345, 1338, 5189, 20122, 78024, 302529, 1172993, 4547973, 
  17633432, 68368135 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=PlusDecomposableAut(xa);</span>
< deterministic automaton on 4 letters with 16 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(a);</span>
[ 0, 1, 3, 11, 47, 196, 808, 3306, 13433, 54265, 218145, 873303, 3483654, 
  13853682, 54945158 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

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

<h5>9.2-2 PlusIndecomposableAut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ PlusIndecomposableAut</code>( <var class="Arg">aut</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An automaton that accepts all permutations of <code class="code">aut</code> that are not plus-decomposable.</p>

<p>The <code class="code">PlusIndecomposableAutomaton</code> automaton accepts the language of all plus-indecomposable permutations of the encoded class accepted by aut, by rejecting every rank encoding that in the original automaton would have entered and left the accept state before the last letter in the rank encodedpermutation.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">xa:=MinimalAutomaton(GraphToAut(Parstacks(2,2),1,6));</span>
< deterministic automaton on 4 letters with 9 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(xa);</span>
[ 1, 2, 6, 23, 89, 345, 1338, 5189, 20122, 78024, 302529, 1172993, 4547973, 
  17633432, 68368135 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=PlusIndecomposableAut(xa);</span>
< deterministic automaton on 4 letters with 11 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(a);</span>
[ 1, 1, 3, 12, 42, 149, 530, 1883, 6689, 23759, 84384, 299690, 1064319, 
  3779750, 13422977 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

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

<h5>9.2-3 MinusDecomposableAut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinusDecomposableAut</code>( <var class="Arg">aut</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An automaton that accepts the subset of the class <code class="code">aut</code> containing the minus-decomposable permutations of <code class="code">aut</code>.</p>

<p>The <code class="code">MinusDecomposableAut</code> automaton accepts the language of all minus-decomposable permutations of the rank encoded class accepted by <code class="code">aut</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">xa:=MinimalAutomaton(GraphToAut(Parstacks(2,2),1,6));</span>
< deterministic automaton on 4 letters with 9 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(xa);</span>
[ 1, 2, 6, 23, 89, 345, 1338, 5189, 20122, 78024, 302529, 1172993, 4547973, 
  17633432, 68368135 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=MinusDecomposableAut(xa);                         </span>
< deterministic automaton on 4 letters with 12 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(a);                                         </span>
[ 0, 1, 3, 10, 24, 64, 180, 520, 1524, 4504, 13380, 39880, 119124, 356344, 
  1066980 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

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

<h5>9.2-4 MinusIndecomposableAut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ MinusIndecomposableAut</code>( <var class="Arg">aut</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An automaton that accepts all permutations of <code class="code">aut</code> that are not minus-decomposable.</p>

<p>The <code class="code">MinusIndecomposableAut</code> automaton accepts the language of all minus-indecomposable permutations of the encoded class accepted by aut, which is the complement set of the set of minus-decomposable permutations within the class.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">xa:=MinimalAutomaton(GraphToAut(Parstacks(2,2),1,6));</span>
< deterministic automaton on 4 letters with 9 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(xa);</span>
[ 1, 2, 6, 23, 89, 345, 1338, 5189, 20122, 78024, 302529, 1172993, 4547973, 
  17633432, 68368135 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=MinusIndecomposableAut(xa);</span>
< deterministic automaton on 4 letters with 17 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(a);</span>
[ 1, 1, 3, 13, 65, 281, 1158, 4669, 18598, 73520, 289149, 1133113, 4428849, 
  17277088, 67301155 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

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

<h4>9.3 <span class="Heading"> Language of all non-simple permutations </span></h4>

<p>The regular language of all non-simple rank encoded permutations with highest rank <span class="SimpleMath">\(k\)</span> is described by the following equation,</p>

<p class="center">\[
    E(NS_{k}) = E(\Omega_{k})
  \cap ( \bigcup_{l=1}^{k-1} P_{l} \bigcup_{m=l}^{k-1} E(\hat{\Omega}_{k-m})^{+m} 
  \cup 
  \bigcup_{j=1}^{k-1} E(\hat{\Omega}_{k-j})^{+j}
  \cup 
\]</p>

<p class="center">\[ 
  \cup
  \bigcup_{a=2}^{k-1} \bigcup_{b=0}^{k-1-a} Q_{a,b} \bigcup_{i=0}^{a-2} (E(\hat{\Omega}_{k-(b+i)})^{+b+i})^{(a-i)} ) \Sigma^{*} 
  \cup 
  E(\mathcal{D}_{P}(\Omega_{k}))
\]</p>

<p>where <span class="SimpleMath">\(\Sigma\)</span> is the alphabet <span class="SimpleMath">\(\{1,\ldots,k\}\)</span>, <span class="SimpleMath">\(k\in\mathbb{N}\)</span>, <span class="SimpleMath">\(k \geq 3\)</span>.</p>

<p><span class="SimpleMath">\(P_{l}\)</span> is the language of prefixes of rank encoded permutations, where the prefix ends with the total sum of gap sizes to be equal to <span class="SimpleMath">\(l\)</span>.</p>

<p><span class="SimpleMath">\(Q_{i,j}\)</span> is the language of prefixes of rank encoded permutations, where the prefix ends with a gap of size <span class="SimpleMath">\(i\)</span> and the sum of the sizes of gaps below equals to <span class="SimpleMath">\(j\)</span>.</p>

<p><span class="SimpleMath">\(E(\Omega_{k-i})^{+i}\)</span> is the language of <span class="SimpleMath">\(E(\Omega_{k-i})\)</span> <span class="SimpleMath">\(i \in \mathbb{N}\)</span>, with the alphabet shifted upwards by <span class="SimpleMath">\(i\)</span>.</p>

<p><span class="SimpleMath">\(E(\Omega_{k})^{(i)}\)</span> is the sublanguage of <span class="SimpleMath">\(E(\Omega_{k})\)</span> containing the words of length <span class="SimpleMath">\(\leq i\)</span>, <span class="SimpleMath">\(i \in \mathbb{N}\)</span>.</p>

<p><span class="SimpleMath">\(E(\hat{\Omega}_{k})\)</span> is the sublanguage of <span class="SimpleMath">\(E(\Omega_{k})\)</span> excluding the words of length <span class="SimpleMath">\(\leq 1\)</span>.</p>

<p><span class="SimpleMath">\(E(\mathcal{D}_{P}(\Omega_{k}))\)</span> is the language of all plus-decomposable permutations as described in <a href="chapBib_mj.html#biBRegLangPlusMinPerms">[HL13]</a>.</p>

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

<h5>9.3-1 LengthBoundAut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ LengthBoundAut</code>( <var class="Arg">aut</var>, <var class="Arg">min</var>, <var class="Arg">i</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The subautomaton of <code class="code">aut</code> that accepts words between (and including) the lengths <code class="code">min</code> and <code class="code">i</code>.</p>

<p>We are taking the automaton <code class="code">aut</code> and it's alphabet k, and find the automaton that accepts all words of aut of length between (and including) min and i.




<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=BoundedClassAutomaton(4); </span>
< deterministic automaton on 4 letters with 4 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(a);</span>
[ 1, 2, 6, 24, 96, 384, 1536, 6144, 24576, 98304, 393216, 1572864, 6291456, 
  25165824, 100663296 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">LengthBoundAut(a,4,8,4);</span>
< deterministic automaton on 4 letters with 22 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(last);</span>
[ 0, 0, 0, 24, 96, 384, 1536, 6144, 0, 0, 0, 0, 0, 0, 0 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

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

<h5>9.3-2 ShiftAut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ShiftAut</code>( <var class="Arg">i</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The automaton <span class="SimpleMath">\(\Omega_{k-i}^{+i}\)</span>.</p>

<p>We are shifting the alphabet of <span class="SimpleMath">\(\Omega_{k-i}\)</span> in their values by <span class="SimpleMath">\(i\)</span> to expand to the alphabet <span class="SimpleMath">\(\{1,\ldots,k\}\)</span>, but keeping the automaton structure of <span class="SimpleMath">\(\Omega_{k-i}\)</span>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ShiftAut(2,4);</span>
< non deterministic automaton on 4 letters with 4 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);</span>
   |  1       2       3       4
-----------------------------------
 a |                                 
 b |                                 
 c | [ 2 ]   [ 4 ]   [ 4 ]   [ 4 ]   
 d | [ 3 ]   [ 3 ]   [ 3 ]   [ 3 ]   
Initial state:   [ 1 ]
Accepting state: [ 4 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ShiftAut(1,4);</span>
< non deterministic automaton on 4 letters with 5 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);</span>
   |  1       2       3       4       5
-------------------------------------------
 a |                                         
 b | [ 2 ]   [ 5 ]   [ 5 ]   [ 3 ]   [ 5 ]   
 c | [ 3 ]   [ 3 ]   [ 3 ]   [ 3 ]   [ 3 ]   
 d | [ 4 ]   [ 4 ]   [ 4 ]   [ 4 ]   [ 4 ]   
Initial state:   [ 1 ]
Accepting state: [ 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

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

<h5>9.3-3 NextGap</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NextGap</code>( <var class="Arg">gap</var>, <var class="Arg">rank</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list of gap sizes.</p>

<p>Knowing the current available gap sizes <code class="code">gap</code>, which are the number of available spaces in a permutation plot. These gaps are separated by blocks where there are already points inserted. We determine where the next point (known to us as its <code class="code">rank</code>) is being placed and what the next gap sizes are.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">NextGap([1,1],2);</span>
[ 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">NextGap([1],3);</span>
[ 1, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">NextGap([2,1],4);</span>
[ 2, 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

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

<h5>9.3-4 GapAut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GapAut</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The non-deterministic automaton accepting the rank encoded language of <span class="SimpleMath">\(\Omega_{k}\)</span> and the list of all possible gap sizes.</p>

<p>The automaton accepts the rank encoded permutations of <span class="SimpleMath">\(\Omega_{k}\)</span>, but the automaton is slightly extended through having each state corresponding to a gap size and the start state being the emptyset of gap sizes. The transitions of the automaton are determined through the knowledge of the available spaces and the rank. This is calculated in <code class="code">NextGap</code>. Please note that the index of the gap sizes in the list corresponds to the state of the automaton.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">GapAut(3);</span>
[ < non deterministic automaton on 3 letters with 5 states >, 
  [ [  ], [ 0 ], [ 1 ], [ 2 ], [ 1, 1 ] ] ]
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last[1]);</span>
   |  1       2       3       4       5
-------------------------------------------
 a | [ 2 ]   [ 2 ]   [ 2 ]   [ 3 ]   [ 3 ]   
 b | [ 3 ]   [ 3 ]   [ 3 ]   [ 3 ]   [ 3 ]   
 c | [ 4 ]   [ 4 ]   [ 5 ]   [ 4 ]   [ 5 ]   
Initial state:    [ 1 ]
Accepting states: [ 1, 2 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"> </span></pre></div>

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

<h5>9.3-5 SumAut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SumAut</code>( <var class="Arg">sum</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The automaton accepting the language <span class="SimpleMath">\(P_{sum}\)</span>.</p>

<p>This automaton is based on the <code class="code">GapAut</code> where the accept states are chosen by their gap sizes, namely if the total sum of gap sizes equal to <code class="code">sum</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">SumAut(2,3);</span>
< non deterministic automaton on 3 letters with 5 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);</span>
   |  1       2       3       4       5
-------------------------------------------
 a | [ 2 ]   [ 2 ]   [ 2 ]   [ 3 ]   [ 3 ]   
 b | [ 3 ]   [ 3 ]   [ 3 ]   [ 3 ]   [ 3 ]   
 c | [ 4 ]   [ 4 ]   [ 5 ]   [ 4 ]   [ 5 ]   
Initial state:    [ 1 ]
Accepting states: [ 4, 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"> </span></pre></div>

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

<h5>9.3-6 GapSumAut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ GapSumAut</code>( <var class="Arg">gap</var>, <var class="Arg">sum</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The automaton accepting the language <span class="SimpleMath">\(Q_{gap,sum}\)</span>.</p>

<p>This automaton is based on the <code class="code">GapAut</code> where the accept states are chosen by their gap sizes, namely if there is a gap size <code class="code">gap</code> and the gap sizes before have a total sum of <code class="code">sum</code>.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">GapSumAut(1,0,3);</span>
< non deterministic automaton on 3 letters with 5 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);   </span>
   |  1       2       3       4       5
-------------------------------------------
 a | [ 2 ]   [ 2 ]   [ 2 ]   [ 3 ]   [ 3 ]   
 b | [ 3 ]   [ 3 ]   [ 3 ]   [ 3 ]   [ 3 ]   
 c | [ 4 ]   [ 4 ]   [ 5 ]   [ 4 ]   [ 5 ]   
Initial state:    [ 1 ]
Accepting states: [ 3, 5 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"> </span></pre></div>

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

<h5>9.3-7 NonSimpleAut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NonSimpleAut</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The automaton accepting all rank encoded non-simple permutations with rank encoding <code class="code">k</code>.</p>

<p>We find the language of all non-simple permutations of the set of all <span class="SimpleMath">\(k\)</span> rank encoded permutations <span class="SimpleMath">\(\Omega_{k}\)</span> using the above equation.</p>


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

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

<h4>9.4 <span class="Heading"> Simplicity </span></h4>

<p>The set of simple permutations of a class is the complement set of the class with the non-simple permutations. We are working in the rank encoding and so in language terms our set of simple permutations <span class="SimpleMath">\(S_{k}\)</span> will be the subset of <span class="SimpleMath">\(\Omega_{k}\)</span></p>

<p class="center">\[
E(S_{k}) = E(\Omega_{k}\setminus NS_{k}) = E(\Omega_{k}) \setminus E(NS_{k}) = E(\Omega_{k}) \cap E(NS_{k})^{C}
\]</p>

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

<h5>9.4-1 SimplePermAut</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ SimplePermAut</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The automaton accepting all rank encoded simple permutations with highest rank encoding <code class="code">k</code>.</p>

<p>We find the language of all simple permutations of the set of all <span class="SimpleMath">\(k\)</span> rank encoded permutations <span class="SimpleMath">\(\Omega_{k}\)</span> using the above equation.</p>


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

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

<h4>9.5 <span class="Heading">Exceptionality</span></h4>

<p>A permutation is said to be exceptional if it is of one of the following forms,</p>

<p class="center">\[
2 4 6 \ldots (2m) 1 3 5 \ldots (2m-1) 
\]</p>

<p class="center">\[
(2m-1) (2m-3) \ldots 1 (2m) (2m-2) \ldots 2
\]</p>

<p class="center">\[
(m+1) 1 (m+2) 2 (m+3) 3 \ldots (2m) m
\]</p>

<p class="center">\[
m (2m) (m-1) (2m-1) \ldots 1 (m+1)
\]</p>

<p>where <span class="SimpleMath">\(m \geq 2\)</span> <a href="chapBib_mj.html#biBSimpPermsPoset">[PR12]</a>.</p>

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

<h5>9.5-1 IsExceptionalPerm</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ IsExceptionalPerm</code>( <var class="Arg">perm</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: <code class="code">True</code> if <code class="code">perm</code> is exceptional, <code class="code">False</code> otherwise.</p>

<p>The functions checks whether <code class="code">perm</code> is one of the 4 types of exceptional permutations, that are described above.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">IsExceptionalPerm([1,2,5,3,4]);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsExceptionalPerm([1,1,3,1,1]);</span>
false
<span class="GAPprompt">gap></span> <span class="GAPinput">IsExceptionalPerm([2,4,6,1,3,5]);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput">IsExceptionalPerm([2,3,4,1,1,1]);</span>
true
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>

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

<h5>9.5-2 ExceptionalBoundedAutomaton</h5>

<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExceptionalBoundedAutomaton</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The automaton which accepts all exceptional permutations with highest rank encoding <code class="code">k</code>.</p>

<p>The language of <code class="code">k</code> rank encoded exceptional permutations will be finite, and so it regular.</p>


<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">ExceptionalBoundedAutomaton(8); </span>
< deterministic automaton on 8 letters with 41 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(last,20);             </span>
[ 0, 2, 0, 2, 0, 4, 0, 4, 0, 2, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ExceptionalBoundedAutomaton(5);</span>
< deterministic automaton on 5 letters with 21 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Spectrum(last);</span>
[ 0, 2, 0, 2, 0, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>


<div class="chlinkprevnextbot"> <a href="chap0_mj.html">[Top of Book]</a>   <a href="chap0_mj.html#contents">[Contents]</a>    <a href="chap8_mj.html">[Previous Chapter]</a>    <a href="chap10_mj.html">[Next Chapter]</a>   </div>


<div class="chlinkbot"><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="chapBib_mj.html">Bib</a>  <a href="chapInd_mj.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>

99%


¤ Dauer der Verarbeitung: 0.22 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.