<p>Permutation pattern classes can be determined using their corresponding basis. The basis of a pattern class is the anti-chain of the class, under the order of containment. A permutation <span class="SimpleMath">π</span> contains another permutation <span class="SimpleMath">σ</span> (of shorter length) if there is a subsequence in <span class="SimpleMath">π</span>, which is isomorphic to <span class="SimpleMath">σ</span>.</p>
<p>With the rational language of the rank encoded class, it is also possible to find the rational language of the basis and vice versa. Several specific kinds of transducers are used in this process. <a href="chapBib.html#biBRegCloSetPerms">[AAR03]</a></p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Transducer</code>( <var class="Arg">states</var>, <var class="Arg">init</var>, <var class="Arg">transitions</var>, <var class="Arg">accepting</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A record that represents a transducer.</p>
<p>A transducer is essentially an automaton, where running through the process does not determine whether the input is accepted, but the input is translated to another language, over a different alphabet.</p>
<p>Formally a transducer is a six-tuple with: <span class="SimpleMath">Q</span> being the set of states, <span class="SimpleMath">S</span> the input alphabet, <span class="SimpleMath">G</span> the output alphabet, <span class="SimpleMath">I ∈ Q</span> the start state, <span class="SimpleMath">A ⊆ Q</span> the set of accept states, and with the transition function <span class="SimpleMath">f: Q × (S ∪ {e}) → Q × (G ∪ {e})</span>, where <span class="SimpleMath">e</span> is the empty word.</p>
<p>In this function the transducer is stored by defining how many states there are, which one (by index) is the start or initial state, the transitions are of the form <code class="code">[inputletter,outputletter,fromstate,tostate]</code> and a list of accept states. The input and output alphabet are determined by the input and output letters on the transitions.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ DeletionTransducer</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A transducer over <code class="code">k</code>+1 states.</p>
<p>A deletion transducer is a transducer that deletes one letter of a rank encoded permutation and returns the correct rank encoding of the new permutation. The deletion transducer over <code class="code">k</code> deletes letters over the set of all rank encoded permutations with highest rank <code class="code">k</code>. Specifically, running through a deletion transducer with a rank encoded permutation, of highest rank <code class="code">k</code>, will lead to the set of all rank encoded permutations that have one letter of the initial permutation removed. It is important to note that computing these shorter permutations with the transducer, is done by reading the inputpermutation from right to left. For example the deletion transducer with <code class="code">k</code>=3, looks as follows:</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ TransposedTransducer</code>( <var class="Arg">t</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A new transducer with interchanged input and output letters on each transition.</p>
<p>A transducer is transposed when all origins and destinations of transitions are left the same as before but the input and output letters on each transition are interchanged. Taking the deletion transducer from above, its transpose looks as follows:</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ InvolvementTransducer</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A transducer over <code class="code">k</code>+1 states, with a <code class="code">k</code> sized alphabet.</p>
<p>An involvement transducer is a transducer over <code class="code">k</code>+1 states, and deletes any number of letters in a rank encoded permutation, of rank at most <code class="code">k</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ CombineAutTransducer</code>( <var class="Arg">aut</var>, <var class="Arg">trans</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An automaton consisting of a combination of <code class="code">aut</code> and <code class="code">trans</code>.</p>
<p>Combining automata and transducers is done over the natural "translation" of the by the automaton accepted language through the transducer and then building a new automaton that accepts the new language. The function <code class="code">CombineAutTransducer</code> does this process and returns the new non-deterministic automaton.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BasisAutomaton</code>( <var class="Arg">a</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An automaton that accepts the rank encoded permutations of the basis of the input automaton <code class="code">a</code>.</p>
<p>Every pattern class has a basis that consists of the smallest set of permutations which do not belong to the class. Using</p>
<p class="pcenter">B(L)=(L^r D^t)^r ∩ L^c</p>
<p>it is possible using the deletion transducer <span class="SimpleMath">D</span> and the language of rank encoded permutations <span class="SimpleMath">L</span> to find the language of the rank encoded permutations of the basis <span class="SimpleMath">B(L)</span>, and thus the basis.</p>
<p>Ignoring the trailing <code class="code">UbUc</code> which essentially are noise, the basis of the pattern class indicates which permutations are avoided in this particular class. The shortest permutation in the basis, looking at the rational expression, is <span class="SimpleMath">daaa</span>, which can be translated to 4111 and decoded to the permutation 4123.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClassAutomaton</code>( <var class="Arg">a</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The automaton that accepts permutations of the class in their rank encoding.</p>
<p>The function <code class="code">ClassAutomaton</code> does the reverse process of <code class="code">BasisAutomaton</code>. Namely it takes the automaton that represents the language of the rank encoded basis of a permutation class, and using the formula</p>
<p>returns the automaton that accepts the rank encoded permutations of the class. In the formula, <span class="SimpleMath">B_k</span> is the automaton that accepts all permutations of any length with highest rank <span class="SimpleMath">k</span>, <span class="SimpleMath">B(L)</span> is the automaton that represents the basis and <span class="SimpleMath">I</span> is the involement transducer.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ BoundedClassAutomaton</code>( <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An automaton that accepts all rank encoded permutations, with highest rank being <code class="code">k</code>.</p>
<p>The bounded class automaton, is an automaton that accepts all rank encoded permutations, of any length, with highest rank <code class="code">k</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">BoundedClassAutomaton(3);</span>
< deterministic automaton on 3 letters with 3 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);</span>
| 1 2 3
--------------
a | 1 1 2
b | 2 2 2
c | 3 3 3
Initial state: [ 1 ]
Accepting state: [ 1 ]
<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">‣ ClassAutFromBaseEncoding</code>( <var class="Arg">base</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The class automaton from a list of rank encoded basis permutations.</p>
<p>Given the permutations in the basis, in their rank encoded form, and the bound of the rank of the permutations of the class, <code class="code">ClassAutFromBaseEncoding</code> builds the automaton that accepts rank encoded permutations of the class.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClassAutFromBase</code>( <var class="Arg">perms</var>, <var class="Arg">k</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The class automaton from a list of permutations of the basis.</p>
<p>Taking <code class="code">perms</code> which is the list of permutations in the basis and <code class="code">k</code> an integer which indicates the highest rank in the encoded permutations of the class, <code class="code">ClassAutFromBase</code> constructs the automaton that accepts the language of rank encoded permutations of the class.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ExpandAlphabet</code>( <var class="Arg">a</var>, <var class="Arg">newAlphabet</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The automaton <code class="code">a</code>, over the alphabet of size <code class="code">newAlphabet</code>.</p>
<p>Given an automaton and the size of the new alphabet, which has to be bigger than the size of the alphabet in <code class="code">a</code> , <code class="code">ExpandAlphabet</code> changes the automaton <code class="code">a</code> to contain an alphabet of size <code class="code">newAlphabet</code>. The new letters have no transitions within the automaton.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">aut:=Automaton("det",3,2,[[2,2,3],[3,3,3]],[1],[3]);</span>
< deterministic automaton on 2 letters with 3 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(aut);</span>
| 1 2 3
--------------
a | 2 2 3
b | 3 3 3
Initial state: [ 1 ]
Accepting state: [ 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput">ExpandAlphabet(aut,4);</span>
< deterministic automaton on 4 letters with 3 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">Display(last);</span>
| 1 2 3
--------------
a | 2 2 3
b | 3 3 3
c |
d |
Initial state: [ 1 ]
Accepting state: [ 3 ]
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>
<h4>6.3 <span class="Heading">Direct Sum of Regular Classes</span></h4>
<p>It is obvious that the direct sum of two rational pattern classes is also rational. But the skew sum of two rational pattern classes does not imply that the resulting pattern class is rational, because if the second class in the sum has infinitely many permutations, the alphabet of the skew sum class will be infinite and thusly the resulting class will not be rational.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ ClassDirectSum</code>( <var class="Arg">aut1</var>, <var class="Arg">aut2</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: An automaton that corresponds to the direct sum of <code class="code">aut1</code> with <code class="code">aut2</code>.</p>
<p><code class="code">ClassDirectSum</code> builds the concatenation automaton of <code class="code">aut1</code> with <code class="code">aut2</code>, which corresponds to the pattern class <codeclass="code">aut1</code> <span class="SimpleMath">⊕</span> <code class="code">aut2</code>.</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">a:=BasisAutomaton(GraphToAut(Parstacks(2,2),1,6)); </span>
< deterministic automaton on 4 letters with 9 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">AutToRatExp(a); </span>
d(a(dbdb)*aaU@)UbUc
<span class="GAPprompt">gap></span> <span class="GAPinput">b:=MinimalAutomaton(GraphToAut(Seqstacks(2,2),1,6));</span>
< deterministic automaton on 3 letters with 3 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">AutToRatExp(b); </span>
((cc*(aUb)Ub)(cc*(aUb)Ub)*aUa)*
<span class="GAPprompt">gap></span> <span class="GAPinput">ab:=ClassDirectSum(a,b); </span>
< deterministic automaton on 4 letters with 11 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">AutToRatExp(ab); </span>
((d(acUc)c*(aUb)Ud(abUb))(cc*(aUb)Ub)*aUda(d(bdbd)*bdbaaUa)UbUc)((cc*(aUb)U\
b)(cc*(aUb)Ub)*aUa)*Ud(aU@)
<span class="GAPprompt">gap></span> <span class="GAPinput"></span></pre></div>
<p>It is of interest to see what permutations and how many of different length are accepted by the class, respectively the basis.</p>
<p>In this section, the examples will be inspecting the basis automaton of the token passing network containing 2 stacks of capacity 2, which are situated in parallel to each other.</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">xa:=GraphToAut(x,1,6);</span>
< epsilon automaton on 5 letters with 66 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">ma:=MinimalAutomaton(xa);</span>
< deterministic automaton on 4 letters with 9 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">ba:=BasisAutomaton(ma);</span>
< deterministic automaton on 4 letters with 9 states >
<span class="GAPprompt">gap></span> <span class="GAPinput">AutToRatExp(ba);</span>
d(a(dbdb)*aaU@)UbUc
<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">‣ Spectrum</code>( <var class="Arg">aut</var>[, <var class="Arg">int</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A list indicating how many words of each length from 1 to <code class="code">int</code> or 15 (default) are accepted by the automaton.</p>
<p>Each entry in the returned list indicates how many words of length the index of the entry are accepted by the automaton <code class="code">aut</code>. The length of the list is by default 15, but if this is too much or too little the second optional argument regulates the length of the list.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ NumberAcceptedWords</code>( <var class="Arg">aut</var>, <var class="Arg">len</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The number of words of length <code class="code">len</code> accepted by the automaton <code class="code">aut</code>.</p>
<p>Given the automaton <code class="code">aut</code> and the integer <code class="code">len</code>, <code class="code">NumberAcceptedWords</code> determines how many words of length <code class="code">len</code> are accepted by the automaton.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AutStateTransitionMatrix</code>( <var class="Arg">aut</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: A matrix containing the number of transitions between states of the automaton <code class="code">aut</code>.</p>
<p>In the matrix computed by <code class="code">AutStateTransitionMatrix</code> the rows are indexed by the state the transitions are originating from, the columnns are indexed by the states the transitions are ending at. Each entry <span class="SimpleMath">a_i,j</span> of the matrix represents the number of transitions from the state <span class="SimpleMath">i</span> to the state <spanclass="SimpleMath">j</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AcceptedWords</code>( <var class="Arg">aut</var>, <var class="Arg">int</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: All words of length <code class="code">int</code> that are accepted by the automaton <code class="code">aut</code>.</p>
<p><code class="code">AcceptedWords</code> outputs all permutations accepted by the automaton <code class="code">aut</code>, which have length <code class="code">int</code>, in a list. The permutations are output in their rank encoding.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AcceptedWordsR</code>( <var class="Arg">aut</var>, <var class="Arg">int1</var>[, <var class="Arg">int2</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ AcceptedWordsReversed</code>( <var class="Arg">aut</var>, <var class="Arg">int1</var>[, <var class="Arg">int2</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>Returns: The list of all by the automaton accepted words of length <code class="code">int1</code>, where each word is written in reverse.</p>
<p>The functions <code class="code">AcceptedWordsR</code> and <code class="code">AcceptedWordsReversed</code> are synonymous and take the following arguments; an automaton <code class="code">aut</code>, an integer <code class="code">int1</code> which indicates the length of the words that are accepted by the <code class="code">aut</code> and another integer <code class="code">int2</code> which is optional and represents the initial state of <code class="code">aut</code>. The return value of these functions is the list containing all permutations of length <code class="code">int1</code> that are accepted by <code class="code">aut</code>. The permutations are rank encoded and written in reverse.</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.
