2022/10/07 by Giulio Cerbai, Cerbai, Giulio
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2210.03621
openalex publication_date 2022/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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-avoiding 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.