Frédérique Bassino ; Mathilde Bouvel ; Adeline Pierrot ; Carine Pivoteau ; Dominique Rossin - Combinatorial specification of permutation classes

dmtcs:3082 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) - https://doi.org/10.46298/dmtcs.3082
Combinatorial specification of permutation classesArticle

Authors: Frédérique Bassino ORCID1; Mathilde Bouvel 2; Adeline Pierrot 3; Carine Pivoteau 4; Dominique Rossin 5

  • 1 Laboratoire d'Informatique de Paris-Nord
  • 2 Laboratoire Bordelais de Recherche en Informatique
  • 3 Laboratoire d'informatique Algorithmique : Fondements et Applications
  • 4 Laboratoire d'Informatique Gaspard-Monge
  • 5 Laboratoire d'informatique de l'École polytechnique [Palaiseau]

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.


Volume: DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: generating functions,simple permutations,substitution decomposition,excluded patterns,permutation classes,combinatorial specification,random generation,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : HAL
  • Méthodes Algorithmiques de Génération aléatoire Non Uniforme, Modèles et applications.; Funder: French National Research Agency (ANR); Code: ANR-10-BLAN-0204

Consultation statistics

This page has been seen 176 times.
This article's PDF has been downloaded 252 times.