chap9.txt

  
  9 Regular Languages of Sets of Permutations
  
  This  chapter  is  dedicated  to the different sets of permutations with the
  same properties.
  
  
  9.1 Inversions in Permutations
  
  An  inversion in a permutation τ=τ_1...τ_n is a pair (i,j) such that 1≤ i<j≤
  n and τ_i>τ_j [5].
  
  9.1-1 InversionAut
  
  InversionAut( k )  function
  Returns:  An   automaton  that  accepts  all  permutations  with  exactly  k
            inversions.
  
  The  rational  language  of  all  permutations  with  a given number , k, of
  inversions is computed by InversionAut.
  
    Example  
    gap> a:=InversionAut(1);
    < deterministic automaton on 2 letters with 4 states >
    gap> AutToRatExp(a);
    a*baa*
    gap> Spectrum(a);     
    [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ]
    gap> b:=InversionAut(5);
    < deterministic automaton on 6 letters with 14 states >
    gap> AutToRatExp(b);
    ((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*
    gap> Spectrum(b);   
    [ 0, 0, 0, 3, 22, 71, 169, 343, 628, 1068, 1717, 2640, 3914, 5629, 7889 ]
    gap> 
  
  
  9.1-2 InversionAutOfClass
  
  InversionAutOfClass( aut, inv )  function
  Returns:  An  automaton  accepting  all  permutations  of  a  class with inv
            inversions.
  
  InversionAutOfClass  intersects the rational pattern class with the rational
  language  containing  all  permutations  under  the  rank encoding that have
  exactly inv inversions.
  
    Example  
    gap> a:=MinimalAutomaton(GraphToAut(Seqstacks(2,2),1,6));
    < deterministic automaton on 3 letters with 3 states >
    gap> Spectrum(a);                                        
    [ 1, 2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366, 118098, 354294, 
      1062882, 3188646 ]
    gap> b:=InversionAutOfClass(a,4);                        
    < deterministic automaton on 5 letters with 23 states >
    gap> Spectrum(b);                                        
    [ 0, 0, 0, 3, 13, 35, 75, 140, 238, 378, 570, 825, 1155, 1573, 2093 ]
    gap> 
  
  
  
  9.2 Plus- and Minus-(In)Decomposablilty
  
  9.2-1 PlusDecomposableAut
  
  PlusDecomposableAut( aut )  function
  Returns:  An  automaton  that accepts the subset of the class aut containing
            the plus-decomposable permutations of aut.
  
  The    PlusDecomposableAut   automaton   accepts   the   language   of   all
  plus-decomposable permutations of the encoded class accepted by aut.
  
    Example  
    gap> xa:=MinimalAutomaton(GraphToAut(Parstacks(2,2),1,6));
    < deterministic automaton on 4 letters with 9 states >
    gap> Spectrum(xa);
    [ 1, 2, 6, 23, 89, 345, 1338, 5189, 20122, 78024, 302529, 1172993, 4547973, 
      17633432, 68368135 ]
    gap> a:=PlusDecomposableAut(xa);
    < deterministic automaton on 4 letters with 16 states >
    gap> Spectrum(a);
    [ 0, 1, 3, 11, 47, 196, 808, 3306, 13433, 54265, 218145, 873303, 3483654, 
      13853682, 54945158 ]
    gap> 
  
  
  9.2-2 PlusIndecomposableAut
  
  PlusIndecomposableAut( aut )  function
  Returns:  An  automaton  that  accepts  all permutations of aut that are not
            plus-decomposable.
  
  The  PlusIndecomposableAutomaton  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.
  
    Example  
    gap> xa:=MinimalAutomaton(GraphToAut(Parstacks(2,2),1,6));
    < deterministic automaton on 4 letters with 9 states >
    gap> Spectrum(xa);
    [ 1, 2, 6, 23, 89, 345, 1338, 5189, 20122, 78024, 302529, 1172993, 4547973, 
      17633432, 68368135 ]
    gap> a:=PlusIndecomposableAut(xa);
    < deterministic automaton on 4 letters with 11 states >
    gap> Spectrum(a);
    [ 1, 1, 3, 12, 42, 149, 530, 1883, 6689, 23759, 84384, 299690, 1064319, 
      3779750, 13422977 ]
    gap> 
  
  
  9.2-3 MinusDecomposableAut
  
  MinusDecomposableAut( aut )  function
  Returns:  An  automaton  that accepts the subset of the class aut containing
            the minus-decomposable permutations of aut.
  
  The   MinusDecomposableAut   automaton   accepts   the   language   of   all
  minus-decomposable permutations of the rank encoded class accepted by aut.
  
    Example  
    gap> xa:=MinimalAutomaton(GraphToAut(Parstacks(2,2),1,6));
    < deterministic automaton on 4 letters with 9 states >
    gap> Spectrum(xa);
    [ 1, 2, 6, 23, 89, 345, 1338, 5189, 20122, 78024, 302529, 1172993, 4547973, 
      17633432, 68368135 ]
    gap> a:=MinusDecomposableAut(xa);                         
    < deterministic automaton on 4 letters with 12 states >
    gap> Spectrum(a);                                         
    [ 0, 1, 3, 10, 24, 64, 180, 520, 1524, 4504, 13380, 39880, 119124, 356344, 
      1066980 ]
    gap> 
  
  
  9.2-4 MinusIndecomposableAut
  
  MinusIndecomposableAut( aut )  function
  Returns:  An  automaton  that  accepts  all permutations of aut that are not
            minus-decomposable.
  
  The   MinusIndecomposableAut   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.
  
    Example  
    gap> xa:=MinimalAutomaton(GraphToAut(Parstacks(2,2),1,6));
    < deterministic automaton on 4 letters with 9 states >
    gap> Spectrum(xa);
    [ 1, 2, 6, 23, 89, 345, 1338, 5189, 20122, 78024, 302529, 1172993, 4547973, 
      17633432, 68368135 ]
    gap> a:=MinusIndecomposableAut(xa);
    < deterministic automaton on 4 letters with 17 states >
    gap> Spectrum(a);
    [ 1, 1, 3, 13, 65, 281, 1158, 4669, 18598, 73520, 289149, 1133113, 4428849, 
      17277088, 67301155 ]
    gap> 
  
  
  
  9.3 Language of all non-simple permutations
  
  The  regular  language  of  all  non-simple  rank  encoded permutations with
  highest rank k is described by the following equation,
  
  
  E(NS_k) = E(Ω_k) ∩ ( ⋃_l=1^k-1 P_l ⋃_m=l^k-1 E(hatΩ_k-m)^+m ∪ ⋃_j=1^k-1 E(hatΩ_k-j)^+j ∪
  
  
  ∪ ⋃_a=2^k-1 ⋃_b=0^k-1-a Q_a,b ⋃_i=0^a-2 (E(hatΩ_k-(b+i))^+b+i)^(a-i) ) Σ^* ∪ E(mathcalD_P(Ω_k))
  
  where Σ is the alphabet {1,...,k}, k∈N, k ≥ 3.
  
  P_l  is  the  language  of  prefixes of rank encoded permutations, where the
  prefix ends with the total sum of gap sizes to be equal to l.
  
  Q_i,j  is  the  language of prefixes of rank encoded permutations, where the
  prefix  ends  with  a  gap  of size i and the sum of the sizes of gaps below
  equals to j.
  
  E(Ω_k-i)^+i  is  the  language  of E(Ω_k-i) i ∈ N, with the alphabet shifted
  upwards by i.
  
  E(Ω_k)^(i)  is the sublanguage of E(Ω_k) containing the words of length ≤ i,
  i ∈ N.
  
  E(hatΩ_k) is the sublanguage of E(Ω_k) excluding the words of length ≤ 1.
  
  E(mathcalD_P(Ω_k))  is the language of all plus-decomposable permutations as
  described in [6].
  
  9.3-1 LengthBoundAut
  
  LengthBoundAut( aut, min, i, k )  function
  Returns:  The subautomaton of aut that accepts words between (and including)
            the lengths min and i.
  
  We  are taking the automaton aut and it's alphabet k, and find the automaton
  that accepts all words of aut of length between (and including) min and i.
  
    Example  
    gap> a:=BoundedClassAutomaton(4); 
    < deterministic automaton on 4 letters with 4 states >
    gap> Spectrum(a);
    [ 1, 2, 6, 24, 96, 384, 1536, 6144, 24576, 98304, 393216, 1572864, 6291456, 
      25165824, 100663296 ]
    gap> LengthBoundAut(a,4,8,4);
    < deterministic automaton on 4 letters with 22 states >
    gap> Spectrum(last);
    [ 0, 0, 0, 24, 96, 384, 1536, 6144, 0, 0, 0, 0, 0, 0, 0 ]
    gap> 
  
  
  9.3-2 ShiftAut
  
  ShiftAut( i, k )  function
  Returns:  The automaton Ω_k-i^+i.
  
  We  are shifting the alphabet of Ω_k-i in their values by i to expand to the
  alphabet {1,...,k}, but keeping the automaton structure of Ω_k-i.
  
    Example  
    gap> ShiftAut(2,4);
    < non deterministic automaton on 4 letters with 4 states >
    gap> Display(last);
       |  1       2       3       4
    -----------------------------------
     a |                                 
     b |                                 
     c | [ 2 ]   [ 4 ]   [ 4 ]   [ 4 ]   
     d | [ 3 ]   [ 3 ]   [ 3 ]   [ 3 ]   
    Initial state:   [ 1 ]
    Accepting state: [ 4 ]
    gap> ShiftAut(1,4);
    < non deterministic automaton on 4 letters with 5 states >
    gap> Display(last);
       |  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 ]
    gap> 
  
  
  9.3-3 NextGap
  
  NextGap( gap, rank )  function
  Returns:  A list of gap sizes.
  
  Knowing  the  current  available  gap  sizes  gap,  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 rank) is being placed and what the next gap sizes are.
  
    Example  
    gap> NextGap([1,1],2);
    [ 1 ]
    gap> NextGap([1],3);
    [ 1, 1 ]
    gap> NextGap([2,1],4);
    [ 2, 1 ]
    gap> 
  
  
  9.3-4 GapAut
  
  GapAut( k )  function
  Returns:  The   non-deterministic   automaton  accepting  the  rank  encoded
            language of Ω_k and the list of all possible gap sizes.
  
  The  automaton  accepts  the  rank  encoded  permutations  of  Ω_k,  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 NextGap. Please note
  that  the index of the gap sizes in the list corresponds to the state of the
  automaton.
  
    Example  
    gap> GapAut(3);
    [ < non deterministic automaton on 3 letters with 5 states >, 
      [ [  ], [ 0 ], [ 1 ], [ 2 ], [ 1, 1 ] ] ]
    gap> Display(last[1]);
       |  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 ]
    gap>  
  
  
  9.3-5 SumAut
  
  SumAut( sum, k )  function
  Returns:  The automaton accepting the language P_sum.
  
  This  automaton is based on the GapAut where the accept states are chosen by
  their gap sizes, namely if the total sum of gap sizes equal to sum.
  
    Example  
    gap> SumAut(2,3);
    < non deterministic automaton on 3 letters with 5 states >
    gap> Display(last);
       |  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 ]
    gap>  
  
  
  9.3-6 GapSumAut
  
  GapSumAut( gap, sum, k )  function
  Returns:  The automaton accepting the language Q_gap,sum.
  
  This  automaton is based on the GapAut where the accept states are chosen by
  their  gap sizes, namely if there is a gap size gap and the gap sizes before
  have a total sum of sum.
  
    Example  
    gap> GapSumAut(1,0,3);
    < non deterministic automaton on 3 letters with 5 states >
    gap> Display(last);   
       |  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 ]
    gap>  
  
  
  9.3-7 NonSimpleAut
  
  NonSimpleAut( k )  function
  Returns:  The  automaton  accepting all rank encoded non-simple permutations
            with rank encoding k.
  
  We find the language of all non-simple permutations of the set of all k rank
  encoded permutations Ω_k using the above equation.
  
    Example  
    gap> a:=NonSimpleAut(3);
    < deterministic automaton on 3 letters with 9 states >
    gap> Display(a);
       |  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 ]
    gap> 
  
  
  
  9.4 Simplicity
  
  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 S_k will be the subset of
  Ω_k
  
  
  E(S_k) = E(Ω_k∖ NS_k) = E(Ω_k) ∖ E(NS_k) = E(Ω_k) ∩ E(NS_k)^C
  
  9.4-1 SimplePermAut
  
  SimplePermAut( k )  function
  Returns:  The  automaton accepting all rank encoded simple permutations with
            highest rank encoding k.
  
  We  find  the  language  of all simple permutations of the set of all k rank
  encoded permutations Ω_k using the above equation.
  
    Example  
    gap> SimplePermAut(3);
    < deterministic automaton on 3 letters with 8 states >
    gap> Display(last);
       |  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 ]
    gap> 
  
  
  
  9.5 Exceptionality
  
  A  permutation  is  said  to be exceptional if it is of one of the following
  forms,
  
  
  2 4 6 ... (2m) 1 3 5 ... (2m-1)
  
  
  (2m-1) (2m-3) ... 1 (2m) (2m-2) ... 2
  
  
  (m+1) 1 (m+2) 2 (m+3) 3 ... (2m) m
  
  
  m (2m) (m-1) (2m-1) ... 1 (m+1)
  
  where m ≥ 2 [7].
  
  9.5-1 IsExceptionalPerm
  
  IsExceptionalPerm( perm )  function
  Returns:  True if perm is exceptional, False otherwise.
  
  The  functions  checks  whether  perm  is  one of the 4 types of exceptional
  permutations, that are described above.
  
    Example  
    gap> IsExceptionalPerm([1,2,5,3,4]);
    false
    gap> IsExceptionalPerm([1,1,3,1,1]);
    false
    gap> IsExceptionalPerm([2,4,6,1,3,5]);
    true
    gap> IsExceptionalPerm([2,3,4,1,1,1]);
    true
    gap> 
  
  
  9.5-2 ExceptionalBoundedAutomaton
  
  ExceptionalBoundedAutomaton( k )  function
  Returns:  The  automaton  which  accepts  all  exceptional permutations with
            highest rank encoding k.
  
  The  language of k rank encoded exceptional permutations will be finite, and
  so it regular.
  
    Example  
    gap> ExceptionalBoundedAutomaton(8); 
    < deterministic automaton on 8 letters with 41 states >
    gap> Spectrum(last,20);             
    [ 0, 2, 0, 2, 0, 4, 0, 4, 0, 2, 0, 2, 0, 2, 0, 0, 0, 0, 0, 0 ]
    gap> ExceptionalBoundedAutomaton(5);
    < deterministic automaton on 5 letters with 21 states >
    gap> Spectrum(last);
    [ 0, 2, 0, 2, 0, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0 ]
    gap>