<h4>9.1 <span class="Heading"> Inversions in Permutations </span></h4>
<p>An inversion in a permutation <span class="SimpleMath">τ=τ_1...τ_n</span> is a pair <span class="SimpleMath">(i,j)</span> such that <span class="SimpleMath">1≤ i<j≤ n</span> and <span class="SimpleMath">τ_i>τ_j</span> <a href="chapBib.html#biBUpBndStanWilf1324">[CJS11]</a>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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 <codeclass="code">inv</code> inversions.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; PlusDecomposableAut</code>( <var class="Arg">aut</var> )</td><tdclass="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="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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>
<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>where <span class="SimpleMath">Σ</span> is the alphabet <span class="SimpleMath">{1,...,k}</span>, <span class="SimpleMath">k∈N</span>, <span class="SimpleMath">k ≥ 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(Ω_k-i)^+i</span> is the language of <span class="SimpleMath">E(Ω_k-i)</span> <span class="SimpleMath">i ∈ N</span>, with the alphabet shifted upwards by <span class="SimpleMath">i</span>.</p>
<p><span class="SimpleMath">E(Ω_k)^(i)</span> is the sublanguage of <span class="SimpleMath">E(Ω_k)</span> containing the words of length <span class="SimpleMath">≤ i</span>, <span class="SimpleMath">i ∈ N</span>.</p>
<p><span class="SimpleMath">E(hatΩ_k)</span> is the sublanguage of <span class="SimpleMath">E(Ω_k)</span> excluding the words of length <span class="SimpleMath">≤ 1</span>.</p>
<p><span class="SimpleMath">E(mathcalD_P(Ω_k))</span> is the language of all plus-decomposable permutations as described in <a href="chapBib.html#biBRegLangPlusMinPerms">[HL13]</a>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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 <code class="code">k</code>, and find the automaton that accepts all words of <code class="code">aut</code> of length between (and including) <code class="code">min</code> and <code class="code">i</code>.</p>
<p>We are shifting the alphabet of <span class="SimpleMath">Ω_k-i</span> in their values by <span class="SimpleMath">i</span> to expand to the alphabet <span class="SimpleMath">{1,...,k}</span>, but keeping the automaton structure of <span class="SimpleMath">Ω_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>
| 1234
-----------------------------------
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>
| 12345
-------------------------------------------
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>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">Ω_k</span> and the list of all possible gap sizes.</p>
<p>The automaton accepts the rank encoded permutations of <span class="SimpleMath">Ω_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="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">Ω_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>
| 123456789
--------------------------------
a | 131531633
b | 333399393
c | 222244274
Initial state: [ 8 ]
Accepting state: [ 1 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>
<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">Ω_k</span></p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">&#an style='color: green'>8227; 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">Ω_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>
| 12345678
-----------------------------
a | 22117216
b | 22422442
c | 22852552
Initial state: [ 3 ]
Accepting states: [ 1, 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>
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 und die Messung sind noch experimentell.
