2013/03/06 by Rebecca Smith, Smith, Rebecca, Vincent Vatter +1
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Advanced Mathematical Identities
paper · pdf · doi:10.48550/arxiv.1303.1395
We study sorting machines consisting of a stack and a pop stack in series, with or without a queue between them. While there are, a priori, four such machines, only two are essentially different: a pop stack followed directly by a stack, and a pop stack followed by a queue and then by a stack. In the former case, we obtain complete answers for the basis and enumeration of the sortable permutations. In the latter case, we present several conjectures.