Two stacks in series: a decreasing stack followed by an increasing stack

DOI10.1007/S00026-014-0227-8MaRDI QIDQ404476zbMATH OpenOpenAlexFDO

Authors Rebecca Smith

Publication date 4 September 2014

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.6801

zbMATH Keywords

data structuresortingstackpermutation pattern

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Searching and sorting (68P10) Combinatorial aspects of partitions of integers (05A17) Combinatorics of partially ordered sets (06A07)

Abstract: We study a sorting machine consisting of two stacks in series where the first stack has the added restriction such that entries in the stack must be in decreasing order from top to bottom. We give the basis of the class of permutations that are sortable by this machine which shows that it is enumerated by the Schr"oder numbers.

Recommendations

• Stack sorting with increasing and decreasing stacks
• A stack and pop stack in series
• Sorting with two ordered stacks in series.
• A bijection on classes enumerated by the Schröder numbers
• Stack sorting with restricted stacks

Cites work

• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• Permutations generated by stacks and deques
• Permutations with forbidden subsequences and a generalized Schröder number
• Postscript: ``Permutations with forbidden subsequences and a generalized Schröder number [Discrete Mathematics 218 (2000) 121--130]
• Sorting with two ordered stacks in series.

Cited in

(16)

• Sorting with pattern-avoiding stacks: the 132-machine
• Passing through a stack \(k\) times with reversals
• Sorting with a popqueue
• 2-stack sorting is polynomial
• A stack and pop stack in series
• A bijection on classes enumerated by the Schröder numbers
• Stack sorting with increasing and decreasing stacks
• Stack sorting with restricted stacks
• Permutations sorted by a finite and an infinite stack in series
• Passing through a stack k times
• Permutations sortable by two stacks in series
• Sorting Cayley permutations with pattern-avoiding machines
• Dynamical aspects of \(\sigma\)-machines
• Catalan and Schröder permutations sortable by two restricted stacks
• Two-stack-sorting with pop stacks
• Sorting with two ordered stacks in series.

This page was built for publication: Two stacks in series: a decreasing stack followed by an increasing stack

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404476)