论文标题
用避开图案的机器对排列进行排序
Sorting permutations with pattern-avoiding machines
论文作者
论文摘要
在这项论文的工作中，我们介绍和研究了一个新的分类设备系列，我们称之为避免模式的机器。它们由两个串联的堆栈组成，配备了贪婪的程序。在两个堆栈上，我们都对图案遏制施加静态约束：从上到下读取内容，第一个堆栈不允许包含给定模式$σ$的出现，而第二个堆栈不允许第二个堆栈包含$ 21 $的出现。通过分析避免模式的机器的行为，我们旨在更好地理解与两个连续堆栈对排列进行分类的问题，这是当前组合术中最具挑战性的开放问题之一。
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.
