Sorting and preimages of pattern classes

Claesson, Anders and Úlfarsson, Henning; (2012) Sorting and preimages of pattern classes. In: 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012). Discrete Mathematics & Theoretical Computer Science, Nancy, France, pp. 595-606. (http://www.dmtcs.org/dmtcs-ojs/index.php/proceedin...)

Full text not available in this repository.Request a copy

Abstract

We introduce an algorithm to determine when a sorting operation, such as stack-sort or bubble-sort, outputs a given pattern. The algorithm provides a new proof of the description of West-2-stack-sortable permutations, that is permutations that are completely sorted when passed twice through a stack, in terms of patterns. We also solve the long-standing problem of describing West-3-stack-sortable permutations. This requires a new type of generalized permutation pattern we call a decorated pattern.

ORCID iDs

Claesson, Anders ORCID logoORCID: https://orcid.org/0000-0001-5797-8673 and Úlfarsson, Henning;
CORE (COnnecting REpositories)