{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T00:36:22Z","timestamp":1768523782935,"version":"3.49.0"},"reference-count":21,"publisher":"EDP Sciences","license":[{"start":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T00:00:00Z","timestamp":1712620800000},"content-version":"vor","delay-in-days":99,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"accepted":{"date-parts":[[2024,2,23]]},"published-print":{"date-parts":[[2024]]},"abstract":"<jats:p>We introduce a new sorting device for permutations, which we call <jats:italic>popqueue<\/jats:italic>. It consists of a special queue, having the property that any time one wants to extract elements from the queue, actually all the elements currently in the queue are poured into the output. We illustrate two distinct optimal algorithms, called Min and Cons, to sort a permutation using such a device, which allow us also to characterize sortable permutations in terms of pattern avoidance. We next investigate what happens by making two passes through a popqueue, showing that the set of sortable permutations is not a class for Min, whereas it is for Cons. In the latter case we also explicitly find the basis of the class of sortable permutations. Finally, we study preimages under Cons (by means of an equivalent version of the algorithm), and find a characterization of the set of preimages of a given permutation. We also give some enumerative results concerning the number of permutations having <jats:italic>k<\/jats:italic> preimages, for <jats:italic>k<\/jats:italic> = 1, 2, 3, and we conclude by observing that there exist permutations having <jats:italic>k<\/jats:italic> preimages for <jats:italic>any<\/jats:italic> value of <jats:italic>k<\/jats:italic> \u2265 0.<\/jats:p>","DOI":"10.1051\/ita\/2024010","type":"journal-article","created":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T08:24:19Z","timestamp":1712651059000},"page":"13","source":"Crossref","is-referenced-by-count":1,"title":["Sorting with a popqueue"],"prefix":"10.1051","volume":"58","author":[{"given":"Lapo","family":"Cioni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Ferrari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,4,9]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Pratt V.R., Computing permutations with double-ended queues. Parallel stacks and parallel queues. Proc. Fifth Annual ACM Symposium on Theory of Computing (1973) 268\u2013277","DOI":"10.1145\/800125.804058"},{"key":"R2","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/321694.321704","volume":"19","author":"Tarjan","year":"1972","journal-title":"J. ACM"},{"key":"R3","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0304-3975(93)90321-J","volume":"117","author":"West","year":"1993","journal-title":"Theoret. Comput. Sci."},{"key":"R4","doi-asserted-by":"crossref","first-page":"105230","DOI":"10.1016\/j.jcta.2020.105230","volume":"173","author":"Cerbai","year":"2020","journal-title":"J. Combin. Theory Ser. A"},{"key":"R5","first-page":"3","volume":"27","author":"Cerbai","year":"2020","journal-title":"Electron. J. Combin."},{"key":"R6","doi-asserted-by":"crossref","first-page":"105275","DOI":"10.1016\/j.jcta.2020.105275","volume":"175","author":"Defant","year":"2020","journal-title":"J. Combin. Theory Ser. A"},{"key":"R7","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/s00026-014-0227-8","volume":"18","author":"Smith","year":"2014","journal-title":"Ann. Comb."},{"key":"R8","unstructured":"West J., Permutations with Forbidden Subsequences and Stack Sortable Permutations. PhD thesis, Massachusetts Institute of Technology (1990)."},{"key":"R9","first-page":"129","volume":"19","author":"Avis","year":"1981","journal-title":"Utilitas Math."},{"key":"R10","first-page":"179","volume":"74","author":"Pudwell","year":"2019","journal-title":"Australas. J. Combin."},{"key":"R11","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.aam.2019.04.002","volume":"108","author":"Claesson","year":"2019","journal-title":"Adv. Appl. Math."},{"key":"R12","unstructured":"Magnusson H., Sorting operators and their preimages. MSc thesis, Reykjavik University (2013)."},{"key":"R13","doi-asserted-by":"crossref","first-page":"112561","DOI":"10.1016\/j.disc.2021.112561","volume":"344","author":"Cioni","year":"2021","journal-title":"Discrete Math."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Cioni L. and Ferrari L., Characterization and enumeration of preimages under the Queuesort algorithm, in Extended Abstracts EuroComb 2021. Trends in Mathematics, Vol. 14, edited by Ne\u0161et\u0159il J., Perarnau G., Ru\u00e9 J., Serra J. and Serra O.. Birkh\u00e4user, Cham.","DOI":"10.1007\/978-3-030-83823-2_37"},{"key":"R15","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/S0012-365X(96)83023-8","volume":"157","author":"West","year":"1996","journal-title":"Discrete Math."},{"key":"R16","unstructured":"Sloane N.J.A., The On-Line Encyclopedia of Integer Sequences. Available at oeis.org."},{"key":"R17","doi-asserted-by":"crossref","first-page":"4.32","DOI":"10.37236\/11390","volume":"29","author":"Bouvel","year":"2022","journal-title":"Electron. J. Combin."},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Foata D. and Sch\u00fctzenberger M.-P., Th\u00e9orie g\u00e9om\u00e9trique des polyn\u00f4mes Eul\u00e9riens. Lecture Notes Math. 138 (1970).","DOI":"10.1007\/BFb0060799"},{"key":"R19","first-page":"527","volume":"11","author":"Defant","year":"2020","journal-title":"J. Comb."},{"key":"R20","doi-asserted-by":"crossref","first-page":"103276","DOI":"10.1016\/j.ejc.2020.103276","volume":"93","author":"Defant","year":"2021","journal-title":"Eur. J. Combin."},{"key":"R21","unstructured":"Lichev L., Lower bound on the running time of Pop-Stack sorting on a random permutation. Available at https:\/\/arxiv.org\/abs\/2212.09316."}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2024010\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T08:24:29Z","timestamp":1712651069000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ita.org\/10.1051\/ita\/2024010"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"references-count":21,"alternative-id":["ita220051"],"URL":"https:\/\/doi.org\/10.1051\/ita\/2024010","relation":{},"ISSN":["0988-3754","2804-7346"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"2804-7346","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]}}}