A stack and pop stack in series
From MaRDI portal
Publication:2875490
zbMATH Open1295.05023arXiv1303.1395MaRDI QIDQ2875490FDOQ2875490
Authors: Rebecca Smith, Vincent Vatter 
Publication date: 15 August 2014
Published in: The Australasian Journal of Combinatorics (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1303.1395
Recommendations
Cited In (16)
- Sorting with a popqueue
- Passing through a stack \(k\) times with reversals
- Ungarian Markov chains
- Two stacks in series: a decreasing stack followed by an increasing stack
- Nine classes of permutations enumerated by binomial transform of Fine's sequence
- Counting Pop-Stacked Permutations in Polynomial Time
- Pop-stacks in parallel
- Combinatorial generation via permutation languages. I: Fundamentals
- Permutations sorted by a finite and an infinite stack in series
- Foot-sorting for socks
- Sorting Cayley permutations with pattern-avoiding machines
- Preimages under a popqueue-sorting algorithm
- Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
- Sorting with a forklift
- Deterministic stack-sorting for set partitions
- Two-stack-sorting with pop stacks
Uses Software
This page was built for publication: A stack and pop stack in series
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875490)
