chap10.txt

  
  10 Miscellaneous functions
  
  This  temporary  chapter  is  dedicated  to miscellaneous functions that are
  relevant to some specific ongoing research questions.
  
  
  10.1 Permutation Inclusion Set
  
  This section is dedicated to the search of the set of permutations which lay
  in between two permutations. Formally that is I_π,ρ = {ρ : π ≤ ρ σ}.
  
  10.1-1 InbetweenPermAutomaton
  
  InbetweenPermAutomaton( perm1, perm2 )  function
  Returns:  An  automaton which accepts the encoded permutations between perm1
            and perm2 where, perm2 is the subpermutation.
  
  InbetweenPermAutomaton   creates   the  intersection  language  between  the
  language   of   all   subpermutations   of   perm1   and   the  language  of
  superpermutations of perm2.
  
    Example  
    	gap> InbetweenPermAutomaton([3,2,1,4,6,5],[1,2]);
    	< deterministic automaton on 3 letters with 8 states >
    	gap> Display(last);
    	   |  1  2  3  4  5  6  7  8
    	-----------------------------
    	 a |  2  2  1  1  6  3  2  6
    	 b |  2  2  4  2  2  4  5  5
    	 c |  2  2  2  2  2  2  2  7
    	Initial state:    [ 8 ]
    	Accepting states: [ 1, 3 ]
    	gap>  
  
  
  10.1-2 InbetweenPermSet
  
  InbetweenPermSet( perm1, perm2 )  function
  Returns:  A  list  which  contains  the permutations between perm1 and perm2
            where, perm2 is the subpermutation.
  
  Using  InbetweenPermAutomaton  we  create the set of all permutations laying
  between the input permutations.
  
    Example  
    gap> InbetweenPermSet([3,2,1,4,6,5],[1,2]);
    [ [ 1, 2 ], [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 1, 2, 4, 3 ],
      [ 2, 1, 3, 4 ], [ 2, 1, 4, 3 ], [ 3, 2, 1, 4 ], [ 2, 1, 3, 5, 4 ],
      [ 3, 2, 1, 4, 5 ], [ 3, 2, 1, 5, 4 ], [ 3, 2, 1, 4, 6, 5 ] ]
    gap> 
  
  
  10.1-3 IsSubPerm
  
  IsSubPerm( perm1, perm2 )  function
  Returns:  true if perm2 is a subpermutation of perm1.
  
  Creates  the  automaton  accepting  all subpermutations of perm1 of the same
  rank  or less, and checks whether the automaton accepts the rank encoding of
  perm2.
  
    Example  
    gap> IsSubPerm([2,4,6,8,1,3,5,7],[2,3,1]);
    true
    gap> IsSubPerm([2,4,6,8,1,3,5,7],[3,2,1]);
    false
    gap> 
  
  
  
  10.2 Automaton Manipulation
  
  10.2-1 LoopFreeAut
  
  LoopFreeAut( aut )  function
  Returns:  An automaton without any loops of length 1.
  
  LoopFreeAut  builds  the subautomaton of aut that does not contain any loops
  of length 1, except for the sink state.
  
    Example  
    gap> a:=Automaton("det",4,3,[[2,4,3,3],[4,4,1,4],[3,1,2,4]],[1],[2]);
    < deterministic automaton on 3 letters with 4 states >
    gap> Display(a);
       |  1  2  3  4
    -----------------
     a |  2  4  3  3
     b |  4  4  1  4
     c |  3  1  2  4
    Initial state:   [ 1 ]
    Accepting state: [ 2 ]
    gap> b:=LoopFreeAut(a);
    < deterministic automaton on 3 letters with 5 states >
    gap> Display(b);
       |  1  2  3  4  5
    --------------------
     a |  2  4  5  3  5
     b |  4  4  1  5  5
     c |  3  1  2  5  5
    Initial state:   [ 1 ]
    Accepting state: [ 2 ]
    gap> 
  
  
  10.2-2 LoopVertexFreeAut
  
  LoopVertexFreeAut( aut )  function
  Returns:  An automaton without any vertices that had loops of length 1.
  
  LoopVertexFreeAut builds the subautomaton that does not contain the vertices
  and transitions of vertices in aut that have loops of length 1. The function
  minimalises  and determinises the automaton before returning it, which might
  change  the  numbering  on  the  vertices,  but  the  returned  automaton is
  isomorphic to the subautomaton of aut.
  
    Example  
    gap> a:=Automaton("det",4,3,[[2,4,3,3],[4,4,1,4],[3,1,2,4]],[1],[2]);
    < deterministic automaton on 3 letters with 4 states >
    gap> Display(a);
       |  1  2  3  4
    -----------------
     a |  2  4  3  3
     b |  4  4  1  4
     c |  3  1  2  4
    Initial state:   [ 1 ]
    Accepting state: [ 2 ]
    gap> b:=LoopVertexFreeAut(a);
    < deterministic automaton on 3 letters with 3 states >
    gap> Display(b);
       |  1  2  3
    --------------
     a |  2  2  1
     b |  2  2  2
     c |  3  2  2
    Initial state:   [ 3 ]
    Accepting state: [ 1 ]
    gap>