In this work of thesis we introduce and study a new family of sorting devices, which we call pattern-avoiding machines. They consist of two stacks in series, equipped with a greedy procedure. On both stacks we impose a static constraint in terms of pattern containment: reading the content from top to bottom, the first stack is not allowed to contain occurrences of a given pattern, whereas the second one is not allowed to contain occurrences of 21. By analyzing the behavior of pattern-avoding machines, we aim to gain a better understanding of the problem of sorting permutations with two consecutive stacks, which is currently one of the most challenging open problems in combinatorics.
Sorting permutations with pattern-avoiding machines / Giulio Cerbai. - (2021).
Sorting permutations with pattern-avoiding machines
Giulio Cerbai
2021
Abstract
In this work of thesis we introduce and study a new family of sorting devices, which we call pattern-avoiding machines. They consist of two stacks in series, equipped with a greedy procedure. On both stacks we impose a static constraint in terms of pattern containment: reading the content from top to bottom, the first stack is not allowed to contain occurrences of a given pattern, whereas the second one is not allowed to contain occurrences of 21. By analyzing the behavior of pattern-avoding machines, we aim to gain a better understanding of the problem of sorting permutations with two consecutive stacks, which is currently one of the most challenging open problems in combinatorics.
| File | Dimensione | Formato | |
|---|---|---|---|
|
G_Cerbai_PhD_Thesis_final_version.pdf
accesso aperto
Descrizione: Tesi di dottorato (referata)
Tipologia:
Versione finale referata (Postprint, Accepted manuscript)
Licenza:
Open Access
Dimensione
973.72 kB
Formato
Adobe PDF
|
973.72 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
