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 classes

Authors: Frédérique Bassino ORCID-iD; Mathilde Bouvel ; Adeline Pierrot ; Carine Pivoteau ; Dominique Rossin

    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]
    Fundings :
      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

    Share

    Consultation statistics

    This page has been seen 112 times.
    This article's PDF has been downloaded 191 times.