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:
Filename Description Size
main.pdfAccepted Manuscript version289.11 kB
Adobe PDF
Full metadata record
© 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: