Sorting with a forklift

MaRDI QIDQ1871364zbMATH OpenFDO

Authors Mike Atkinson, Michael Albert

Publication date 7 May 2003

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

Full work available at URL https://arxiv.org/abs/cs/0209016, https://eudml.org/doc/122594, http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i2r9.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

permutationsortable sequences

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Exact enumeration problems, generating functions (05A15)

Abstract: A fork stack is a generalised stack which allows pushes and pops of several items at a time. We consider the problem of determining which input streams can be sorted using a single forkstack, or dually, which permutations of a fixed input stream can be produced using a single forkstack. An algorithm is given to solve the sorting problem and the minimal unsortable sequences are found. The results are extended to fork stacks where there are bounds on how many items can be pushed and popped at one time. In this context we also establish how to enumerate the collection of sortable sequences.

Recommendations

• Sorting with a Forklift
• Sorting with two ordered stacks in series.
• A stack and pop stack in series
• A survey of stack-sorting disciplines
• 2-stack sorting is polynomial

Cited in

(3)

• Sorting with a Forklift
• On the least exponential growth admitting uncountably many closed permutation classes
• Sorting with networks of data structures

This page was built for publication: Sorting with a forklift

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