Ferrari, Luca
(2013)

*Permutation classes, sorting algorithms, and lattice paths*, [Dissertation thesis], Alma Mater Studiorum Università di Bologna.
Dottorato di ricerca in

Matematica, 25 Ciclo. DOI 10.6092/unibo/amsdottorato/6032.

Documenti full-text disponibili:

## Abstract

A permutation is said to avoid a pattern if it does not contain any subsequence which is order-isomorphic to it. Donald Knuth, in the first volume of his celebrated book "The art of Computer Programming", observed that the permutations that can be computed (or, equivalently, sorted) by some particular data structures can be characterized in terms of pattern avoidance. In more recent years, the topic was reopened several times, while often in terms of sortable permutations rather than computable ones.
The idea to sort permutations by using one of Knuth’s devices suggests to look for a deterministic procedure that decides, in linear time, if there exists a sequence of operations which is able to convert a given permutation into the identical one.
In this thesis we show that, for the stack and the restricted deques, there exists an unique way to implement such a procedure. Moreover, we use these sorting procedures to create new sorting algorithms, and we prove some unexpected commutation properties between these procedures and the base step of bubblesort. We also show that the permutations that can be sorted by a combination of the base steps of bubblesort and its dual can be expressed, once again, in terms of pattern avoidance.
In the final chapter we give an alternative proof of some enumerative results, in particular for the classes of permutations that can be sorted by the two restricted deques. It is well-known that the permutations that can be sorted through a restricted deque are counted by the Schrӧder numbers. In the thesis, we show how the deterministic sorting procedures yield a bijection between sortable permutations and Schrӧder paths.

Abstract

A permutation is said to avoid a pattern if it does not contain any subsequence which is order-isomorphic to it. Donald Knuth, in the first volume of his celebrated book "The art of Computer Programming", observed that the permutations that can be computed (or, equivalently, sorted) by some particular data structures can be characterized in terms of pattern avoidance. In more recent years, the topic was reopened several times, while often in terms of sortable permutations rather than computable ones.
The idea to sort permutations by using one of Knuth’s devices suggests to look for a deterministic procedure that decides, in linear time, if there exists a sequence of operations which is able to convert a given permutation into the identical one.
In this thesis we show that, for the stack and the restricted deques, there exists an unique way to implement such a procedure. Moreover, we use these sorting procedures to create new sorting algorithms, and we prove some unexpected commutation properties between these procedures and the base step of bubblesort. We also show that the permutations that can be sorted by a combination of the base steps of bubblesort and its dual can be expressed, once again, in terms of pattern avoidance.
In the final chapter we give an alternative proof of some enumerative results, in particular for the classes of permutations that can be sorted by the two restricted deques. It is well-known that the permutations that can be sorted through a restricted deque are counted by the Schrӧder numbers. In the thesis, we show how the deterministic sorting procedures yield a bijection between sortable permutations and Schrӧder paths.

Tipologia del documento

Tesi di dottorato

Autore

Ferrari, Luca

Supervisore

Dottorato di ricerca

Scuola di dottorato

Scienze matematiche, fisiche ed astronomiche

Ciclo

25

Coordinatore

Settore disciplinare

Settore concorsuale

Parole chiave

permutation class device stack queue deque sorting deterministic greedy procedure algorithm bubblesort stacksort dual commutation lattice path dyck schrӧder enumeration bijection

URN:NBN

DOI

10.6092/unibo/amsdottorato/6032

Data di discussione

19 Giugno 2013

URI

## Altri metadati

Tipologia del documento

Tesi di dottorato

Autore

Ferrari, Luca

Supervisore

Dottorato di ricerca

Scuola di dottorato

Scienze matematiche, fisiche ed astronomiche

Ciclo

25

Coordinatore

Settore disciplinare

Settore concorsuale

Parole chiave

permutation class device stack queue deque sorting deterministic greedy procedure algorithm bubblesort stacksort dual commutation lattice path dyck schrӧder enumeration bijection

URN:NBN

DOI

10.6092/unibo/amsdottorato/6032

Data di discussione

19 Giugno 2013

URI

## Statistica sui download

Gestione del documento: