\(k\)-pop stack sortable permutations and \(2\)-avoidance (Q2662333)

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.