Geodesic
Combinatorial specification of permutation 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).

Voir la notice de l'article provenant de la source Episciences

This article presents a methodology that automatically derives a combinatorial specification for the permutation class $\mathcal{C} = Av(B)$, given its basis $B$ of excluded patterns and the set of simple permutations in $\mathcal{C}$, when these sets are both finite. This is achieved considering both pattern avoidance and pattern containment constraints in permutations.The obtained specification yields a system of equations satisfied by the generating function of $\mathcal{C}$, this system being always positive and algebraic. It also yields a uniform random sampler of permutations in $\mathcal{C}$. The method presented is fully algorithmic. 
@article{DMTCS_2012_special_263_a68,
     author = {Bassino, Fr\'ed\'erique and Bouvel, Mathilde and Pierrot, Adeline and Pivoteau, Carine and Rossin, Dominique},
     title = {Combinatorial specification of permutation classes},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)},
     year = {2012},
     doi = {10.46298/dmtcs.3082},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3082/}
}
TY  - JOUR
AU  - Bassino, Frédérique
AU  - Bouvel, Mathilde
AU  - Pierrot, Adeline
AU  - Pivoteau, Carine
AU  - Rossin, Dominique
TI  - Combinatorial specification of permutation 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)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3082/
DO  - 10.46298/dmtcs.3082
LA  - en
ID  - DMTCS_2012_special_263_a68
ER  - 
%0 Journal Article
%A Bassino, Frédérique
%A Bouvel, Mathilde
%A Pierrot, Adeline
%A Pivoteau, Carine
%A Rossin, Dominique
%T Combinatorial specification of permutation 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)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3082/
%R 10.46298/dmtcs.3082
%G en
%F DMTCS_2012_special_263_a68
Bassino, Frédérique; Bouvel, Mathilde; Pierrot, Adeline; Pivoteau, Carine; Rossin, Dominique. Combinatorial specification of permutation 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.3082. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3082/

Cité par Sources :