Permutations sorted by a finite and an infinite stack in series


Abstract in English

We prove that the set of permutations sorted by a stack of depth $t geq 3$ and an infinite stack in series has infinite basis, by constructing an infinite antichain. This answers an open question on identifying the point at which, in a sorting process with two stacks in series, the basis changes from finite to infinite.

Download