GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it

1
  
2
  6 Pattern Classes
3
  
4
  Permutation  pattern  classes  can  be  determined using their corresponding
5
  basis.  The  basis  of a pattern class is the anti-chain of the class, under
6
  the order of containment. A permutation π contains another permutation σ (of
7
  shorter length) if there is a subsequence in π, which is isomorphic to σ.
8
  
9
  With the rational language of the rank encoded class, it is also possible to
10
  find  the  rational  language  of the basis and vice versa. Several specific
11
  kinds of transducers are used in this process. [2]
12
  
13
  
14
  6.1 Transducers
15
  
16
  6.1-1 Transducer
17
  
18
  Transducer( states, init, transitions, accepting )  function
19
  Returns:  A record that represents a transducer.
20
  
21
  A  transducer is essentially an automaton, where running through the process
22
  does  not  determine  whether  the  input  is  accepted,  but  the  input is
23
  translated to another language, over a different alphabet.
24
  
25
  Formally  a transducer is a six-tuple with: Q being the set of states, S the
26
  input  alphabet, G the output alphabet, I ∈ Q the start state, A ⊆ Q the set
27
  of accept states, and with the transition function f: Q × (S ∪ {e}) → Q × (G
28
  ∪ {e}), where e is the empty word.
29
  
30
  In  this function the transducer is stored by defining how many states there
31
  are, which one (by index) is the start or initial state, the transitions are
32
  of  the  form  [inputletter,outputletter,fromstate,tostate]  and  a  list of
33
  accept states. The input and output alphabet are determined by the input and
34
  output letters on the transitions.
35
  
36
    Example  
37
    gap> trans:=Transducer(3,1,[[1,2,1,2],[1,2,2,2],[2,2,1,3],[2,2,2,3],
38
    > [1,1,3,3],[2,2,3,3]],[2]);
39
    rec( accepting := [ 2 ], initial := 1, states := 3, 
40
      transitions := [ [ 1, 2, 1, 2 ], [ 1, 2, 2, 2 ], [ 2, 2, 1, 3 ], 
41
          [ 2, 2, 2, 3 ], [ 1, 1, 3, 3 ], [ 2, 2, 3, 3 ] ] )
42
    gap> 
43
  
44
  
45
  6.1-2 DeletionTransducer
46
  
47
  DeletionTransducer( k )  function
48
  Returns:  A transducer over k+1 states.
49
  
50
  A  deletion  transducer  is  a  transducer that deletes one letter of a rank
51
  encoded  permutation  and  returns  the  correct  rank  encoding  of the new
52
  permutation.  The deletion transducer over k deletes letters over the set of
53
  all  rank  encoded  permutations  with highest rank k. Specifically, running
54
  through  a  deletion  transducer with a rank encoded permutation, of highest
55
  rank  k, will lead to the set of all rank encoded permutations that have one
56
  letter  of  the  initial  permutation  removed. It is important to note that
57
  computing these shorter permutations with the transducer, is done by reading
58
  the  input  permutation  from  right  to  left.  For  example  the  deletion
59
  transducer with k=3, looks as follows:
60
  
61
    Example  
62
    gap> DeletionTransducer(3);
63
    rec( accepting := [ 1 .. 3 ], initial := 4, states := 4, 
64
      transitions := [ [ 1, 1, 4, 4 ], [ 1, 0, 4, 1 ], [ 2, 1, 1, 1 ], 
65
          [ 1, 1, 1, 2 ], [ 3, 2, 1, 1 ], [ 1, 1, 2, 3 ], [ 1, 1, 3, 3 ], 
66
          [ 2, 2, 4, 4 ], [ 2, 0, 4, 2 ], [ 3, 2, 2, 2 ], [ 2, 2, 2, 3 ], 
67
          [ 2, 2, 3, 3 ], [ 3, 3, 4, 4 ], [ 3, 0, 4, 3 ], [ 3, 3, 3, 3 ] ] )
68
    gap> 
69
  
70
  
71
  6.1-3 TransposedTransducer
72
  
73
  TransposedTransducer( t )  function
74
  Returns:  A  new  transducer  with  interchanged input and output letters on
75
            each transition.
76
  
77
  A  transducer is transposed when all origins and destinations of transitions
78
  are  left  the  same  as  before  but  the  input and output letters on each
79
  transition  are interchanged. Taking the deletion transducer from above, its
80
  transpose looks as follows:
81
  
82
    Example  
83
    gap> TransposedTransducer(DeletionTransducer(3));
84
    rec( accepting := [ 1 .. 3 ], initial := 4, states := 4, 
85
      transitions := [ [ 1, 1, 4, 4 ], [ 0, 1, 4, 1 ], [ 1, 2, 1, 1 ], 
86
          [ 1, 1, 1, 2 ], [ 2, 3, 1, 1 ], [ 1, 1, 2, 3 ], [ 1, 1, 3, 3 ], 
87
          [ 2, 2, 4, 4 ], [ 0, 2, 4, 2 ], [ 2, 3, 2, 2 ], [ 2, 2, 2, 3 ], 
88
          [ 2, 2, 3, 3 ], [ 3, 3, 4, 4 ], [ 0, 3, 4, 3 ], [ 3, 3, 3, 3 ] ] )
89
    gap> 
90
  
91
  
92
  6.1-4 InvolvementTransducer
93
  
94
  InvolvementTransducer( k )  function
95
  Returns:  A transducer over k+1 states, with a k sized alphabet.
96
  
97
  An  involvement  transducer is a transducer over k+1 states, and deletes any
98
  number of letters in a rank encoded permutation, of rank at most k.
99
  
100
    Example  
101
    gap> InvolvementTransducer(3);
102
    rec( accepting := [ 1 .. 4 ], initial := 4, states := 4, 
103
      transitions := [ [ 1, 1, 1, 2 ], [ 1, 0, 1, 3 ], [ 2, 1, 1, 1 ], 
104
          [ 2, 0, 1, 3 ], [ 3, 2, 1, 1 ], [ 3, 0, 1, 1 ], [ 1, 1, 2, 4 ], 
105
          [ 1, 0, 2, 1 ], [ 2, 2, 2, 4 ], [ 2, 0, 2, 2 ], [ 3, 2, 2, 2 ], 
106
          [ 3, 0, 2, 2 ], [ 1, 1, 3, 2 ], [ 1, 0, 3, 3 ], [ 2, 1, 3, 1 ], 
107
          [ 2, 0, 3, 3 ], [ 3, 1, 3, 3 ], [ 3, 0, 3, 3 ], [ 1, 1, 4, 4 ], 
108
          [ 1, 0, 4, 1 ], [ 2, 2, 4, 4 ], [ 2, 0, 4, 2 ], [ 3, 3, 4, 4 ], 
109
          [ 3, 0, 4, 4 ] ] )
110
    gap> 
111
  
112
  
113
  6.1-5 CombineAutTransducer
114
  
115
  CombineAutTransducer( aut, trans )  function
116
  Returns:  An automaton consisting of a combination of aut and trans.
117
  
118
  Combining automata and transducers is done over the natural "translation" of
119
  the  by  the  automaton  accepted  language  through the transducer and then
120
  building  a  new  automaton  that  accepts  the  new  language. The function
121
  CombineAutTransducer does this process and returns the new non-deterministic
122
  automaton.
123
  
124
    Example  
125
    gap> a:=Automaton("det",1,1,[[1]],[1],[1]);
126
    < deterministic automaton on 1 letters with 1 states >
127
    gap> AutToRatExp(a);
128
    a*
129
    gap> t:=Transducer(2,1,[[1,2,1,2],[2,1,1,2],
130
    > [1,1,2,1],[2,2,2,1]],[1]);
131
    rec( accepting := [ 1 ], initial := 1, states := 2, 
132
      transitions := [ [ 1, 2, 1, 2 ], [ 2, 1, 1, 2 ], [ 1, 1, 2, 1 ], 
133
          [ 2, 2, 2, 1 ] ] )
134
    gap> res:=CombineAutTransducer(a,t);
135
    < non deterministic automaton on 2 letters with 2 states >
136
    gap> AutToRatExp(res);
137
    (ba)*
138
    gap> Display(res);
139
       |  1       2
140
    -------------------
141
     a |         [ 1 ]   
142
     b | [ 2 ]           
143
    Initial state:   [ 1 ]
144
    Accepting state: [ 1 ]
145
    gap> 
146
  
147
  
148
  
149
  6.2 From Class to Basis and vice versa
150
  
151
  6.2-1 BasisAutomaton
152
  
153
  BasisAutomaton( a )  function
154
  Returns:  An  automaton  that  accepts  the rank encoded permutations of the
155
            basis of the input automaton a.
156
  
157
  Every  pattern  class  has  a  basis  that  consists  of the smallest set of
158
  permutations which do not belong to the class. Using
159
  
160
  
161
  B(L)=(L^r D^t)^r ∩ L^c
162
  
163
  it  is  possible  using  the  deletion transducer D and the language of rank
164
  encoded permutations L to find the language of the rank encoded permutations
165
  of the basis B(L), and thus the basis.
166
  
167
    Example  
168
    gap> x:=Parstacks(2,2);
169
    [ [ 2, 4 ], [ 3, 6 ], [ 2 ], [ 5, 6 ], [ 4 ], [  ] ]
170
    gap> xa:=GraphToAut(x,1,6);
171
    < epsilon automaton on 5 letters with 66 states >
172
    gap> ma:=MinimalAutomaton(xa);
173
    < deterministic automaton on 4 letters with 9 states >
174
    gap> Display(ma);
175
       |  1  2  3  4  5  6  7  8  9  
176
    --------------------------------
177
     a |  1  2  1  3  2  2  6  6  3  
178
     b |  3  2  3  3  4  3  6  9  3  
179
     c |  9  2  9  4  6  6  4  9  9  
180
     d |  8  2  8  7  5  5  7  8  8  
181
    Initial state:   [ 1 ]
182
    Accepting state: [ 1 ]
183
    gap> ba:=BasisAutomaton(ma);
184
    < deterministic automaton on 4 letters with 9 states >
185
    gap> Display(ba);
186
       |  1  2  3  4  5  6  7  8  9  
187
    --------------------------------
188
     a |  2  2  1  3  4  2  2  2  2  
189
     b |  2  2  2  2  2  4  1  2  8  
190
     c |  2  2  2  2  2  2  1  2  2  
191
     d |  2  2  2  9  2  2  5  6  2  
192
    Initial state:    [ 7 ]
193
    Accepting states: [ 1, 5 ]
194
    gap> AutToRatExp(ba);
195
    d(a(dbdb)*aaU@)UbUc
196
    gap> 
197
  
198
  
199
  Ignoring  the  trailing  UbUc  which essentially are noise, the basis of the
200
  pattern  class  indicates  which permutations are avoided in this particular
201
  class.  The  shortest  permutation  in  the  basis,  looking at the rational
202
  expression,  is  daaa,  which  can  be translated to 4111 and decoded to the
203
  permutation 4123.
204
  
205
  6.2-2 ClassAutomaton
206
  
207
  ClassAutomaton( a )  function
208
  Returns:  The automaton that accepts permutations of the class in their rank
209
            encoding.
210
  
211
  The  function  ClassAutomaton  does  the  reverse process of BasisAutomaton.
212
  Namely  it  takes  the  automaton  that  represents the language of the rank
213
  encoded basis of a permutation class, and using the formula
214
  
215
  
216
  L=B_k ∩ ((B(L)^r I^t)^c )^r
217
  
218
  returns  the  automaton  that  accepts  the rank encoded permutations of the
219
  class. In the formula, B_k is the automaton that accepts all permutations of
220
  any  length  with  highest rank k, B(L) is the automaton that represents the
221
  basis and I is the involement transducer.
222
  
223
    Example  
224
    gap> xa:=Automaton("det",9,4,[[2,2,1,3,4,2,2,2,2],[2,2,2,2,2,4,1,2,8],
225
    > [2,2,2,2,2,2,1,2,2],[2,2,2,9,2,2,5,6,2]],[7],[1,5]); 
226
    < deterministic automaton on 4 letters with 9 states >
227
    gap> ca:=ClassAutomaton(xa); 
228
    < deterministic automaton on 4 letters with 9 states >
229
    gap> Display(ca);
230
       |  1  2  3  4  5  6  7  8  9  
231
    --------------------------------
232
     a |  1  2  1  3  2  2  6  6  3  
233
     b |  3  2  3  3  4  3  6  9  3  
234
     c |  9  2  9  4  6  6  4  9  9  
235
     d |  8  2  8  7  5  5  7  8  8  
236
    Initial state:   [ 1 ]
237
    Accepting state: [ 1 ]
238
    gap> IsPossibleGraphAut(ca);
239
    true
240
    gap> 
241
  
242
  
243
  6.2-3 BoundedClassAutomaton
244
  
245
  BoundedClassAutomaton( k )  function
246
  Returns:  An  automaton  that  accepts  all  rank encoded permutations, with
247
            highest rank being k.
248
  
249
  The  bounded  class automaton, is an automaton that accepts all rank encoded
250
  permutations, of any length, with highest rank k.
251
  
252
    Example  
253
    gap> BoundedClassAutomaton(3);
254
    < deterministic automaton on 3 letters with 3 states >
255
    gap> Display(last);
256
       |  1  2  3  
257
    --------------
258
     a |  1  1  2  
259
     b |  2  2  2  
260
     c |  3  3  3  
261
    Initial state:   [ 1 ]
262
    Accepting state: [ 1 ]
263
    gap> 
264
  
265
  
266
  6.2-4 ClassAutFromBaseEncoding
267
  
268
  ClassAutFromBaseEncoding( base, k )  function
269
  Returns:  The   class   automaton   from   a  list  of  rank  encoded  basis
270
            permutations.
271
  
272
  Given  the  permutations  in  the basis, in their rank encoded form, and the
273
  bound of the rank of the permutations of the class, ClassAutFromBaseEncoding
274
  builds the automaton that accepts rank encoded permutations of the class.
275
  
276
    Example  
277
    gap> ClassAutFromBaseEncoding([[4,1,1,1]],4); 
278
    < deterministic automaton on 4 letters with 7 states >
279
    gap> Display(last);
280
       |  1  2  3  4  5  6  7  
281
    --------------------------
282
     a |  1  2  1  3  2  2  6  
283
     b |  3  2  3  3  4  3  4  
284
     c |  4  2  4  4  6  6  4  
285
     d |  7  2  7  7  5  5  7  
286
    Initial state:   [ 1 ]
287
    Accepting state: [ 1 ]
288
    gap> 
289
  
290
  
291
  6.2-5 ClassAutFromBase
292
  
293
  ClassAutFromBase( perms, k )  function
294
  Returns:  The class automaton from a list of permutations of the basis.
295
  
296
  Taking perms which is the list of permutations in the basis and k an integer
297
  which  indicates  the highest rank in the encoded permutations of the class,
298
  ClassAutFromBase  constructs the automaton that accepts the language of rank
299
  encoded permutations of the class.
300
  
301
    Example  
302
    gap> ClassAutFromBase([[4,1,2,3]],4);
303
    < deterministic automaton on 4 letters with 7 states >
304
    gap> Display(last);
305
       |  1  2  3  4  5  6  7  
306
    --------------------------
307
     a |  1  2  1  3  2  2  6  
308
     b |  3  2  3  3  4  3  4  
309
     c |  4  2  4  4  6  6  4  
310
     d |  7  2  7  7  5  5  7  
311
    Initial state:   [ 1 ]
312
    Accepting state: [ 1 ]
313
    gap> 
314
  
315
  
316
  6.2-6 ExpandAlphabet
317
  
318
  ExpandAlphabet( a, newAlphabet )  function
319
  Returns:  The automaton a, over the alphabet of size newAlphabet.
320
  
321
  Given  an automaton and the size of the new alphabet, which has to be bigger
322
  than  the size of the alphabet in a , ExpandAlphabet changes the automaton a
323
  to  contain  an  alphabet  of  size  newAlphabet.  The  new  letters have no
324
  transitions within the automaton.
325
  
326
    Example  
327
    gap> aut:=Automaton("det",3,2,[[2,2,3],[3,3,3]],[1],[3]);
328
    < deterministic automaton on 2 letters with 3 states >
329
    gap> Display(aut);
330
       |  1  2  3  
331
    --------------
332
     a |  2  2  3  
333
     b |  3  3  3  
334
    Initial state:   [ 1 ]
335
    Accepting state: [ 3 ]
336
    gap> ExpandAlphabet(aut,4);
337
    < deterministic automaton on 4 letters with 3 states >
338
    gap> Display(last);
339
       |  1  2  3  
340
    --------------
341
     a |  2  2  3  
342
     b |  3  3  3  
343
     c |           
344
     d |           
345
    Initial state:   [ 1 ]
346
    Accepting state: [ 3 ]
347
    gap> 
348
  
349
  
350
  
351
  6.3 Direct Sum of Regular Classes
352
  
353
  It  is  obvious  that the direct sum of two rational pattern classes is also
354
  rational.  But  the  skew sum of two rational pattern classes does not imply
355
  that the resulting pattern class is rational, because if the second class in
356
  the sum has infinitely many permutations, the alphabet of the skew sum class
357
  will be infinite and thusly the resulting class will not be rational.
358
  
359
  6.3-1 ClassDirectSum
360
  
361
  ClassDirectSum( aut1, aut2 )  function
362
  Returns:  An automaton that corresponds to the direct sum of aut1 with aut2.
363
  
364
  ClassDirectSum  builds  the concatenation automaton of aut1 with aut2, which
365
  corresponds to the pattern class aut1 ⊕ aut2.
366
  
367
    Example  
368
    gap> a:=BasisAutomaton(GraphToAut(Parstacks(2,2),1,6));  
369
    < deterministic automaton on 4 letters with 9 states >
370
    gap> AutToRatExp(a);                                     
371
    d(a(dbdb)*aaU@)UbUc
372
    gap> b:=MinimalAutomaton(GraphToAut(Seqstacks(2,2),1,6));
373
    < deterministic automaton on 3 letters with 3 states >
374
    gap> AutToRatExp(b);                                     
375
    ((cc*(aUb)Ub)(cc*(aUb)Ub)*aUa)*
376
    gap> ab:=ClassDirectSum(a,b);                            
377
    < deterministic automaton on 4 letters with 11 states >
378
    gap> AutToRatExp(ab);                                    
379
    ((d(acUc)c*(aUb)Ud(abUb))(cc*(aUb)Ub)*aUda(d(bdbd)*bdbaaUa)UbUc)((cc*(aUb)U\
380
    b)(cc*(aUb)Ub)*aUa)*Ud(aU@)
381
    gap> 
382
  
383
  
384
  
385
  6.4 Statistical Inspections
386
  
387
  It  is of interest to see what permutations and how many of different length
388
  are accepted by the class, respectively the basis.
389
  
390
  In  this section, the examples will be inspecting the basis automaton of the
391
  token  passing network containing 2 stacks of capacity 2, which are situated
392
  in parallel to each other.
393
  
394
    Example  
395
    gap> x:=Parstacks(2,2);
396
    [ [ 2, 4 ], [ 3, 6 ], [ 2 ], [ 5, 6 ], [ 4 ], [  ] ]
397
    gap> xa:=GraphToAut(x,1,6);
398
    < epsilon automaton on 5 letters with 66 states >
399
    gap> ma:=MinimalAutomaton(xa);
400
    < deterministic automaton on 4 letters with 9 states >
401
    gap> ba:=BasisAutomaton(ma);
402
    < deterministic automaton on 4 letters with 9 states >
403
    gap> AutToRatExp(ba);
404
    d(a(dbdb)*aaU@)UbUc
405
    gap> 
406
  
407
  
408
  6.4-1 Spectrum
409
  
410
  Spectrum( aut[, int] )  function
411
  Returns:  A  list  indicating how many words of each length from 1 to int or
412
            15 (default) are accepted by the automaton.
413
  
414
  Each entry in the returned list indicates how many words of length the index
415
  of the entry are accepted by the automaton aut. The length of the list is by
416
  default  15,  but  if  this  is  too  much or too little the second optional
417
  argument regulates the length of the list.
418
  
419
    Example  
420
    gap> Spectrum(ba);
421
    [ 3, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 ]
422
    gap> Spectrum(ba,20);
423
    [ 3, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1 ]
424
    gap> 
425
  
426
  
427
  6.4-2 NumberAcceptedWords
428
  
429
  NumberAcceptedWords( aut, len )  function
430
  Returns:  The number of words of length len accepted by the automaton aut.
431
  
432
  Given  the automaton aut and the integer len, NumberAcceptedWords determines
433
  how many words of length len are accepted by the automaton.
434
  
435
    Example  
436
    gap> NumberAcceptedWords(ba,1);
437
    3
438
    gap> NumberAcceptedWords(ba,16);
439
    1
440
    gap> 
441
  
442
  
443
  6.4-3 AutStateTransitionMatrix
444
  
445
  AutStateTransitionMatrix( aut )  function
446
  Returns:  A  matrix  containing  the number of transitions between states of
447
            the automaton aut.
448
  
449
  In  the  matrix computed by AutStateTransitionMatrix the rows are indexed by
450
  the  state the transitions are originating from, the columnns are indexed by
451
  the  states  the  transitions  are ending at. Each entry a_i,j of the matrix
452
  represents the number of transitions from the state i to the state j.
453
  
454
    Example  
455
    gap> AutStateTransitionMatrix(ba);
456
    [ [ 0, 4, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 4, 0, 0, 0, 0, 0, 0, 0 ], 
457
      [ 1, 3, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 2, 1, 0, 0, 0, 0, 0, 1 ], 
458
      [ 0, 3, 0, 1, 0, 0, 0, 0, 0 ], [ 0, 3, 0, 1, 0, 0, 0, 0, 0 ], 
459
      [ 2, 1, 0, 0, 1, 0, 0, 0, 0 ], [ 0, 3, 0, 0, 0, 1, 0, 0, 0 ], 
460
      [ 0, 3, 0, 0, 0, 0, 0, 1, 0 ] ]
461
    gap> 
462
  
463
  
464
  6.4-4 AcceptedWords
465
  
466
  AcceptedWords( aut, int )  function
467
  Returns:  All words of length int that are accepted by the automaton aut.
468
  
469
  AcceptedWords  outputs all permutations accepted by the automaton aut, which
470
  have  length  int,  in  a  list.  The  permutations are output in their rank
471
  encoding.
472
  
473
    Example  
474
    gap> AcceptedWords(ba,1);
475
    [ [ 2 ], [ 3 ], [ 4 ] ]
476
    gap> AcceptedWords(ba,16);
477
    [ [ 4, 1, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 1, 1 ] ]
478
    gap> 
479
  
480
  
481
  6.4-5 AcceptedWordsR
482
  
483
  AcceptedWordsR( aut, int1[, int2] )  function
484
  AcceptedWordsReversed( aut, int1[, int2] )  function
485
  Returns:  The  list  of  all by the automaton accepted words of length int1,
486
            where each word is written in reverse.
487
  
488
  The  functions  AcceptedWordsR  and AcceptedWordsReversed are synonymous and
489
  take  the  following  arguments;  an  automaton  aut,  an integer int1 which
490
  indicates  the  length of the words that are accepted by the aut and another
491
  integer  int2 which is optional and represents the initial state of aut. The
492
  return  value  of these functions is the list containing all permutations of
493
  length  int1 that are accepted by aut. The permutations are rank encoded and
494
  written in reverse.
495
  
496
    Example  
497
    gap> AcceptedWordsR(ba,1);
498
    [ [ 2 ], [ 3 ], [ 4 ] ]
499
    gap> AcceptedWordsReversed(ba,16); 
500
    [ [ 1, 1, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 2, 4, 1, 4 ] ]
501
    gap> 
502
  
503
  
504

505