Orderings on words and permutations

Ordered sets;Combinatorial analysis;Permutations

McDevitt, Matthew ; Ruškuc, Nik ; Ruškuc, Nik

University:University of St Andrews

Department:Mathematics & Statistics (School of)

关键词: Ordered sets;    Combinatorial analysis;    Permutations;   

Others  :  https://research-repository.st-andrews.ac.uk/bitstream/handle/10023/18465/MatthewMcDevittPhDThesis.pdf?sequence=2&isAllowed=y

来源: DR-NTU

【 摘 要 】

Substructure orderings are ubiquitous throughout combinatorics and all of mathematics.In this thesis we consider various orderings on words, as well as the consecutiveinvolvement ordering on permutations. Throughout there will be a focuson deciding certain order-theoretic properties, primarily the properties of being well-quasi-ordered(WQO) and of being atomic.In Chapter 1, we establish the background material required for the remainder ofthe thesis. This will include concepts from order theory, formal language theory, automatatheory, and the theory of permutations. We also introduce various orderingson words, and the consecutive involvement ordering on permutations.In Chapter 2, we consider the prefix, suffix and factor orderings on words. For theprefix and suffix orderings, we give a characterisation of the regular languages whichare WQO, and of those which are atomic. We then consider the factor ordering andshow that the atomicity is decidable for finitely-based sets. We also give a new proofthat WQO is decidable for finitely-based sets, which is a special case of a result ofAtminas et al.In Chapters 3 and 4, we consider some general families of orderings on words. InChapter 3 we consider orderings on words which are rational, meaning that they canbe generated by transducers. We discuss the class of insertion relations introducedin a paper by the author, and introduce a generalisation. In Chapter 4, weconsider three other variations of orderings on words. Throughout these chapters weprove various decidability results.In Chapter 5, we consider the consecutive involvement on permutations. We generaliseour results for the factor ordering on words to show that WQO and atomicityare decidable. Through this investigation we answer some questions which have beenasked (and remain open) for the involvement on permutations.