GAP (PatternClass) - Chapter 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_{\pi,\rho} = \{\rho : \pi \leq \rho \sigma\} \).

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.

	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.

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 )

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.

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 )

LoopFreeAut builds the subautomaton of aut that does not contain any loops of length 1, except for the sink state.

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 )

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.

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>