The enumeration of permutations sortable by pop stacks in parallel
We show that the set of permutations sortable by k pop stacks in parallel has a regular insertion encoding and construct the (finite) recognizing automaton for this language. This shows that these permutations have a rational generating function, verifying a conjecture of Atkinson and Sack. (c) 2009 Elsevier B.V. All rights reserved.
permutation pop stack insertion encoding algorithms data structures sorting