Geodesic
Sorting and preimages of pattern classes
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) (2012) Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

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. 
@article{DMTCS_2012_special_263_a52,
     author = {Claesson, Anders and \'Ulfarsson, Henning},
     title = {Sorting and preimages of pattern classes},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2012},
     volume = {DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)},
     doi = {10.46298/dmtcs.3066},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3066/}
}
TY  - JOUR
AU  - Claesson, Anders
AU  - Úlfarsson, Henning
TI  - Sorting and preimages of pattern classes
JO  - Discrete mathematics & theoretical computer science
PY  - 2012
VL  - DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3066/
DO  - 10.46298/dmtcs.3066
LA  - en
ID  - DMTCS_2012_special_263_a52
ER  - 
%0 Journal Article
%A Claesson, Anders
%A Úlfarsson, Henning
%T Sorting and preimages of pattern classes
%J Discrete mathematics & theoretical computer science
%D 2012
%V DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3066/
%R 10.46298/dmtcs.3066
%G en
%F DMTCS_2012_special_263_a52
Claesson, Anders; Úlfarsson, Henning. Sorting and preimages of pattern classes. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) (2012). doi: 10.46298/dmtcs.3066

Cité par Sources :