Permutations Sorted by a Finite and an Infinite Stack in Series
- Publication Type:
- Conference Proceeding
- Lecture Notes in Computer Science, 2018, 10792 pp. 220 - 231 (12)
- Issue Date:
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: