Permutations Sorted by a Finite and an Infinite Stack in Series

Publisher:
Springer
Publication Type:
Conference Proceeding
Citation:
Lecture Notes in Computer Science, 2018, 10792 pp. 220 - 231 (12)
Issue Date:
2018-04-05
Full metadata record
Files in This Item:
Filename Description Size
main.pdfAccepted Manuscript version289.11 kB
Adobe PDF
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: