A stack and pop stack in series

MaRDI QIDQ2875490zbMATH OpenFDO

Authors Rebecca Smith, Vincent Vatter

Publication date 15 August 2014

Published in The Australasian Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.1395, http://ajc.maths.uq.edu.au/pdf/58/ajc_v58_p157.pdf

zbMATH Keywords

sorting machinesenumeration of the sortable permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05)

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.

Recommendations

• Two stacks in series: a decreasing stack followed by an increasing stack
• Two-stack-sorting with pop stacks
• Stack sorting with increasing and decreasing stacks
• Sorting with two ordered stacks in series.
• Stack sorting with restricted stacks

Cited in

(16)

• Nine classes of permutations enumerated by binomial transform of Fine's sequence
• Sorting with a popqueue
• Counting Pop-Stacked Permutations in Polynomial Time
• Two-stack-sorting with pop stacks
• Sorting Cayley permutations with pattern-avoiding machines
• Passing through a stack \(k\) times with reversals
• Two stacks in series: a decreasing stack followed by an increasing stack
• Foot-sorting for socks
• Pop-stacks in parallel
• Permutations sorted by a finite and an infinite stack in series
• Preimages under a popqueue-sorting algorithm
• Ungarian Markov chains
• Deterministic stack-sorting for set partitions
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• Combinatorial generation via permutation languages. I: Fundamentals
• Sorting with a forklift

Describes a project that uses

Uses Software

• OEIS
• PermLab

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)