Permutations Sorted by a Finite and an infinite stack in series
- Publication Type:
- Conference Proceeding
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2018, 10792 LNCS pp. 220 - 231
- Issue Date:
© Springer International Publishing AG, part of Springer Nature 2018. We prove that the set of permutations sorted by a stack of depth t ≥ 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.
Please use this identifier to cite or link to this item: