2013/03/18 by Adeline Pierrot, Pierrot, Adeline, Dominique Rossin +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1303.4376
openalex publication_date 2013/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the 60's, Knuth introduced stack-sorting and serial compositions of stacks. In particular, one significant question arise out of the work of Knuth: how to decide efficiently if a given permutation is sortable with 2 stacks in series? Whether this problem is polynomial or NP-complete is still unanswered yet. In this article we introduce 2-stack pushall permutations which form a subclass of 2-stack sortable permutations and show that these two classes are closely related. Moreover, we give an optimal O(n2) algorithm to decide if a given permutation of size n is 2-stack pushall sortable and describe all its sortings. This result is a step to the solve the general 2-stack sorting problem in polynomial time.