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