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

DOI10.1007/S00026-014-0227-8zbMATH Open1297.05011arXiv1301.6801OpenAlexW2063451706MaRDI QIDQ404476FDOQ404476

Rebecca Smith

Publication date: 4 September 2014

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

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.

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)

Cites Work

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

Cited In (8)

• Sorting with a popqueue
• Passing through a stack \(k\) times with reversals
• Sorting with pattern-avoiding stacks: the \(132\)-machine
• Stack sorting with increasing and decreasing stacks
• Stack sorting with restricted stacks
• Passing through a stack k times
• Sorting Cayley permutations with pattern-avoiding machines
• Dynamical aspects of \(\sigma\)-machines

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)