Sorting operators and their preimages
Hjalti Magnússon · 2013
Þessi ritgerð byggir a þeirri vinnu Claessons og Ulfarssonar sem snýr að reikniritum sem finna formyndir mynsturflokka undir staflaroðunarvirkjanum. Við skoðum einnig aðrar roðunaraðferðir, þ.e. roðun með stafla af takmarkaðri dýpt, roðun með biðroð, roðun með togstafla, innsetningarroðun og ponnukokuroðun, og gefum sambaerileg reiknirit fyrir þaer. Við kynnum einnig til sogunnar yfirmynstur sem gera okkur kleift að samraema framsetningu reikniritanna. Við sýnum jafnframt hvernig reiknirit Claesson og Ulfarssonar, fyrir formyndir staflaroðunar, er haegt að utfaera til þess að finna formyndir akveðins flokks moskvamynstra. Þannig ma sjalfvirknivaeða sonnun a lýsingu þeirra umraðana sem haegt er að raða með þremur itrunum af staflaroðun. Að lokum sýnum við hvernig samskeyting a staflaroðunar- og biðrararoðunarvirkjunum gefur reiknirit sem akvarðar, a linulegum tima, hvort umroðun innihaldi klassiska mynstrið 4312.; This thesis extends previous work of Claesson and Ulfarsson (2012) on algorithms for computing the preimage of a pattern class under the stack-sort operator. We consider several other sorting operators, namely stacks of fixed depth, queues, pop-stacks, insertion sort and pancake sort, and find corresponding algorithms for them. We also introduce the notion of meta patterns that allow us to present these algorithms in a uniform way. Furthermore, we consider how Claesson's and Ulfarsson's original algorithm for stack-sort can be extended to find the preimage of a mesh pattern class. This enables us to give an automatic proof of the description of West-3-stack-sortable permutations. Finally we show how the combination of the stack-sort and queue-sort operators can be used to create a linear time algorithm for determining avoidance of the pattern 4312.