How Many Pop-Stacks Does It Take To Sort A Permutation?. (6th July 2021)
- Record Type:
- Journal Article
- Title:
- How Many Pop-Stacks Does It Take To Sort A Permutation?. (6th July 2021)
- Main Title:
- How Many Pop-Stacks Does It Take To Sort A Permutation?
- Authors:
- Albert, Michael
Vatter, Vincent - Abstract:
- Abstract: Pop-stacks are variants of stacks that were introduced by Avis and Newborn in 1981. Coincidentally, a 1982 result of Unger implies that every permutation of length $n$ can be sorted by $n-1$ passes through a deterministic pop-stack. We give a new proof of this result inspired by Knuth's zero-one principle.
- Is Part Of:
- Computer journal. Volume 65:Number 10(2022)
- Journal:
- Computer journal
- Issue:
- Volume 65:Number 10(2022)
- Issue Display:
- Volume 65, Issue 10 (2022)
- Year:
- 2022
- Volume:
- 65
- Issue:
- 10
- Issue Sort Value:
- 2022-0065-0010-0000
- Page Start:
- 2610
- Page End:
- 2614
- Publication Date:
- 2021-07-06
- Subjects:
- pop-stacks -- permutation patterns -- sorting
Computers -- Periodicals
005.1 - Journal URLs:
- http://comjnl.oxfordjournals.org/ ↗
http://ukcatalogue.oup.com/ ↗ - DOI:
- 10.1093/comjnl/bxab092 ↗
- Languages:
- English
- ISSNs:
- 0010-4620
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3394.060000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 24093.xml