On dots in boxes, or Permutation pattern classes and regular languages

Computer science--Mathematics;Formal languages;Permutations

Hoffmann, Ruth ; Linton, Steve ; Linton, Steve

University:University of St Andrews

Department:Computer Science (School of)

关键词: Computer science--Mathematics;    Formal languages;    Permutations;   

Others  :  https://research-repository.st-andrews.ac.uk/bitstream/handle/10023/7034/RuthHoffmanPhDThesis.pdf?sequence=3&isAllowed=y

来源: DR-NTU

【 摘 要 】

This thesis investigates permutation pattern classes in a language theoretic context. Specificallywe explored the regularity of sets of permutations under the rank encoding. We found that thesubsets of plus- and minus-(in)decomposable permutations of a regular pattern class under therank encoding are also regular languages under that encoding. Further we investigated the sets ofpermutations, which in their block-decomposition have the same simple permutation, and againwe found that these sets of permutations are regular languages under the rank encoding. Thisnatural progression from plus- and minus-decomposable to simple decomposable permutations ledus further to the set of simple permutations under the rank encoding, which we have also shownto be regular under the rank encoding. This regular language enables us to find the set of simplepermutations of any class, independent of whether the class is regular under the rank encoding.Furthermore the regularity of the languages of some types of classes is discussed. Under therank encoding we show that in general the skew-sum of classes, separable classes and wreath classesare not regular languages; but that the direct-sum of classes, and with some restrictions on thecardinality of the input classes the skew-sum and wreath sum of classes in fact are regular underthis encoding.Other encodings such as the insertion encoding and the geometric grid encoding are discussedand in the case of the geometric grid encoding alternative and constructive ways of retrieving thebasis of a geometric grid class are suggested.The aforementioned results of the rank encoding have been implemented, amongst other previouslyshown results, and tested. The program is available and accessible to everyone. We showthat the implementation for finding the block-decomposition of a permutation has cubic time complexitywith respect to the length of the permutation. The code for constructing the automatonthat accepts the language of all plus-indecomposable permutations of a regular class under therank encoding has quadratic time complexity with respect to the alphabet of the language. Theprocedure to find the automaton that accepts the language of minus-decomposable permutationshas complexity O(k⁵) and we show that the implementation of the automaton to find the languageof simple permutations under the rank encoding has time complexity O(k⁵ 2ᵏ), where k is the sizeof the alphabet. Further we show benchmark testing on previous important results involving therank encoding on classes and their bases.