\(k\)-pop stack sortable permutations and \(2\)-avoidance (Q2662333)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(k\)-pop stack sortable permutations and \(2\)-avoidance |
scientific article |
Statements
\(k\)-pop stack sortable permutations and \(2\)-avoidance (English)
0 references
12 April 2021
0 references
Pop stacks are restricted versions of stacks that must pop their entire contents when they pop. They were introduced by \textit{D. Avis} and \textit{M. Newborn} [Util. Math. 19, 129--140 (1981; Zbl 0461.68060)], although this paper considers a deterministic algorithm for pop stack sorting that was not considered until later. In this paper it is proved that for any integer \(k\), the set of permutations that can be sorted by \(k\) passes through a deterministic pop stack can be described in a finite manner, thereby answering a question of [\textit{A. Claesson} and \textit{B. Á. Guðmundsson}, Adv. Appl. Math. 108, 79--96 (2019; Zbl 1415.05012)]. This finite manner consists of a finite description in terms of ``\(2\)-avoidance''. Examples are given contrasting \(2\)-avoidance to barred patterns avoidance and mesh pattern avoidance.
0 references
permutation pattern
0 references
stack sorting
0 references
0 references