{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:04:56Z","timestamp":1772370296702,"version":"3.50.1"},"reference-count":15,"publisher":"Oxford University Press (OUP)","license":[{"start":{"date-parts":[[2021,7,6]],"date-time":"2021-07-06T00:00:00Z","timestamp":1625529600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["636113"],"award-info":[{"award-number":["636113"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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\u2019s zero-one principle.<\/jats:p>","DOI":"10.1093\/comjnl\/bxab092","type":"journal-article","created":{"date-parts":[[2021,6,14]],"date-time":"2021-06-14T19:11:00Z","timestamp":1623697860000},"source":"Crossref","is-referenced-by-count":2,"title":["How Many Pop-Stacks Does It Take To Sort A Permutation?"],"prefix":"10.1093","author":[{"given":"Michael","family":"Albert","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Otago, Dunedin 9054, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Vatter","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,7,6]]},"reference":[{"key":"2021071005232928800_ref1","volume-title":"The Art of Computer Programming","author":"Knuth","year":"1968"},{"key":"2021071005232928800_ref2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0304-3975(93)90321-J","article-title":"Sorting twice through a stack","volume":"117","author":"West","year":"1993","journal-title":"Theoret. Comput. Sci."},{"key":"2021071005232928800_ref3","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0012-365X(92)90351-F","article-title":"A proof of Julian West\u2019s conjecture that the number of two-stack-sortable permutations of length n is 2(3n)!\/((n+1)!(2n+1)!)","volume":"102","author":"Zeilberger","year":"1992","journal-title":"Discrete Math."},{"key":"2021071005232928800_ref4","first-page":"129","article-title":"On pop-stacks in series","volume":"19","author":"Avis","year":"1981","journal-title":"Utilitas Math."},{"key":"2021071005232928800_ref5","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0097-3165(82)90045-0","article-title":"2N noncollinear points determine at least 2N directions","volume":"33","author":"Ungar","year":"1982","journal-title":"J. Combin. Theory Ser. A"},{"key":"2021071005232928800_ref6","volume-title":"The Art of Computer Programming","author":"Knuth","year":"1973"},{"key":"2021071005232928800_ref7","article-title":"Describing West-3-stack-sortable permutations with permutation patterns","volume":"67","author":"\u00dalfarsson","year":"2012","journal-title":"S\u00e9m. Lothar. Combin."},{"key":"2021071005232928800_ref8","article-title":"k-pop stack sortable permutations and 2-avoidance","volume":"28","author":"Elder","journal-title":"Electron. J. Combin."},{"key":"2021071005232928800_ref9","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1007\/s00224-016-9743-8","article-title":"2-stack sorting is polynomial","volume":"60","author":"Pierrot","year":"2017","journal-title":"Theory Comput. Syst."},{"key":"2021071005232928800_ref10","first-page":"179","article-title":"Two-stack-sorting with pop stacks","volume":"74","author":"Pudwell","year":"2019","journal-title":"Australas. J. Combin."},{"key":"2021071005232928800_ref11","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.aam.2019.04.002","article-title":"Enumerating permutations sortable by k passes through a pop-stack","volume":"108","author":"Claesson","year":"2019","journal-title":"Adv. in Appl. Math."},{"key":"2021071005232928800_ref12","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/S0012-365X(02)00443-0","article-title":"Restricted permutations and the wreath product","volume":"259","author":"Atkinson","year":"2002","journal-title":"Discrete Math."},{"key":"2021071005232928800_ref13","first-page":"395","article-title":"Pop-stack sorting and its image: permutations with overlapping runs","volume":"88","author":"Asinowski","year":"2019","journal-title":"Acta Math. Univ. Comenian. (N.S.)"},{"key":"2021071005232928800_ref14","first-page":"39","article-title":"Flip-sort and combinatorial aspects of pop-stack sorting","volume":"22","author":"Asinowski","year":"2021","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"2021071005232928800_ref15","doi-asserted-by":"crossref","DOI":"10.1016\/j.ejc.2020.103276","article-title":"Fertility monotonicity and average complexity of the stack-sorting map","volume":"93","author":"Defant","year":"2021","journal-title":"European J. Combin."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/advance-article-pdf\/doi\/10.1093\/comjnl\/bxab092\/38891328\/bxab092.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comjnl\/advance-article-pdf\/doi\/10.1093\/comjnl\/bxab092\/38891328\/bxab092.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,10]],"date-time":"2021-07-10T08:30:25Z","timestamp":1625905825000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/advance-article\/doi\/10.1093\/comjnl\/bxab092\/6316088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,6]]},"references-count":15,"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxab092","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,6]]},"article-number":"bxab092"}}