1############################################################################### 2## This program is free software: you can redistribute it and/or modify 3## it under the terms of the GNU General Public License as published by 4## the Free Software Foundation, either version 2 of the License, or 5## (at your option) any later version. 6## 7## This program is distributed in the hope that it will be useful, 8## but WITHOUT ANY WARRANTY; without even the implied warranty of 9## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10## GNU General Public License for more details. 11## 12#W decomp.gd Ruth Hoffmann 13## 14## 15#Y Copyright (C) 2004-2015 School of Computer Science, 16#Y University of St. Andrews, North Haugh, 17#Y St. Andrews, Fife KY16 9SS, Scotland 18## 19 20################################################################################ 21## 22#F IsPlusDecomposable(perm) 23## 24## IsPlusDecomposable uses the fact that there has to be an interval 1..x where 25## x<n (n=length of the permutation) in the permutation that is a rank encoding, 26## to check whether perm is a plus-decomposable permutation. 27## 28## Side Note: The permutation [1,2] (encoded as [1,1]) is seen as a 29## plus-decomposable permutation, as it displays the characteristics of such 30## a permutation, eventhough it is also a simple permutation. 31## 32DeclareGlobalFunction( "IsPlusDecomposable" ); 33 34################################################################################ 35## 36#F IsMinusDecomposable(perm) 37## 38## IsMinusDecomposable checks whether the permutation perm is minus decomposable 39## by checking whether the complement of the permutation is plus decomposable. 40## 41## Side Note: The permutation [2,1] (encoded as [2,1]) is seen as a 42## minus-decomposable permutation, as it displays the characteristics of such 43## a permutation, eventhough it is also a simple permutation. 44## 45DeclareGlobalFunction( "IsMinusDecomposable" ); 46 47################################################################################ 48## 49#F IsSimplePerm(perm) 50## 51## IsSimplePerm checks whether the permutation perm is simple, i.e. there are no 52## non-trivial intervals within perm. 53## 54DeclareGlobalFunction( "IsSimplePerm" ); 55 56################################################################################ 57## 58#F PlusIndecomposableAut(aut) 59## 60## The PlusIndecomposableAutomaton accepts the language of all 61## plus-indecomposable permutations of the encoded class accepted by aut. 62## 63DeclareGlobalFunction( "PlusIndecomposableAut" ); 64################################################################################ 65DeclareSynonym("PlusIndecompAut",PlusIndecomposableAut ); 66 67################################################################################ 68## 69#F PlusDecomposableAut(aut) 70## 71## The PlusDecomposableAutomaton accepts the language of all 72## plus-decomposable permutations of the encoded class accepted by aut. 73## 74DeclareGlobalFunction( "PlusDecomposableAut" ); 75################################################################################ 76DeclareSynonym("PlusDecompAut",PlusDecomposableAut ); 77 78################################################################################ 79## 80#F LdkAut(d,k) 81## 82## LdkAut is an auxiliary function to build an intermediate automaton, which 83## will be used to build the automaton that accepts all minus-decomposable 84## permutations of a class. The LdkAut automaton accepts the language 85## {{1,..d}^d {d+1,..k}^+} . 86## 87DeclareGlobalFunction( "LdkAut" ); 88 89################################################################################ 90## 91#F LAut(k) 92## 93## LAut is another auxiliary function to build an intermediate automaton, which 94## will be used to build the automaton that accepts all minus-decomposable 95## permutations of a class. LAut is the union of LdkAut over the range of d in 96## [1..k-1] . 97## 98DeclareGlobalFunction( "LAut" ); 99 100################################################################################ 101## 102#F MinusDecomposableAut(aut) 103## 104## MinusDecomposableAut finds the regular language that is build by all simple 105## permutations of the encoded class accepted by aut. 106## 107DeclareGlobalFunction( "MinusDecomposableAut" ); 108################################################################################ 109DeclareSynonym("MinusDecompAut",MinusDecomposableAut); 110 111################################################################################ 112## 113#F MinusIndecomposableAut(aut) 114## 115## MinusIndecomposableAut(aut) finds the automaton that accepts the subset of 116## minus-indecomposable permutations of the class accepted by aut. 117## 118DeclareGlobalFunction( "MinusIndecomposableAut" ); 119################################################################################ 120DeclareSynonym("MinusIndecompAut",MinusIndecomposableAut); 121 122################################################################################ 123## 124#F PermDirectSum(perm1,perm2) 125## 126## PermDirectSum calculates and returns the resulting permutation of the direct 127## sum of the permutations perm1 and perm2. 128## 129DeclareGlobalFunction( "PermDirectSum" ); 130 131################################################################################ 132## 133#F PermSkewSum(perm1,perm2) 134## 135## PermSkewSum calculates and returns the resulting permutation of the skew 136## sum of the permutations perm1 and perm2. 137## 138DeclareGlobalFunction( "PermSkewSum" ); 139 140################################################################################ 141## 142#F ClassDirectSum(aut1,aut2) 143## 144## ClassDirectSum builds the automaton of a class that represents the resulting 145## class of the direct sum of the regular classes aut1 and aut2. 146## 147DeclareGlobalFunction( "ClassDirectSum" ); 148 149################################################################################ 150## 151#F Inflation(decomposition) 152## 153## Inflation takes the list of permutations that stand for the box decomposition 154## representing a permutation, and calculates that permutation. 155## 156DeclareGlobalFunction( "Inflation" ); 157 158 159################################################################################ 160## 161#F IsInterval(list) 162## 163## IsInterval takes in any sublist of a permutation and checkes whether it is 164## an interval. 165## 166DeclareGlobalFunction( "IsInterval" ); 167 168################################################################################ 169## 170#F BlockDecomposition(perm) 171## 172## BlockDecomposition takes a plus- and minus-indecomposable permutation and 173## decomposes it into its maximal maximal intervals, which are preceded by the 174## simple permutation that represents the positions of the intervals. 175## If a plus- or minus-decomposable permutation is input, then the decomposition 176## will not be the unique decomposition, by the definition of plus- or minus- 177## decomposable permutations. 178## 179DeclareGlobalFunction( "BlockDecomposition" ); 180