How Many Pop-Stacks Does It Take To Sort A Permutation?. (6th July 2021) - Albert, Michael; Vatter, Vincent
Abstract: Pop-stacks are variants of stacks that were introduced by Avis and Newborn in 1981. Coincidentally, a 1982 result of Unger implies that every permutation of length $n$ can be sorted by $n-1$ passes through a deterministic pop-stack. We give a new proof of this result inspired by Knuth's zero-one principle.