Combinatorial specification of permutation classes
| العنوان: | Combinatorial specification of permutation classes |
|---|---|
| المؤلفون: | Frédérique Bassino, Adeline Pierrot, Dominique Rossin, Mathilde Bouvel, Carine Pivoteau |
| المساهمون: | Laboratoire d'Informatique de Paris-Nord (LIPN), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), ANR-10-BLAN-0204,MAGNUM,Méthodes Algorithmiques de Génération aléatoire Non Uniforme, Modèles et applications.(2010), Université Sorbonne Paris Cité (USPC)-Institut Galilée-Université Paris 13 (UP13)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X) |
| المصدر: | HAL Discrete Mathematics and Theoretical Computer Science 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), Jul 2012, Nagoya, Japan. pp.781-792, ⟨10.46298/dmtcs.3082⟩ 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), Jul 2012, Nagoya, Japan. pp.781-792 |
| مصطلحات موضوعية: | Class (set theory), General Computer Science, substitution decomposition, simple permutations, System of linear equations, Theoretical Computer Science, Set (abstract data type), Combinatorics, Permutation, excluded patterns, Simple (abstract algebra), ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, generating functions, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Algebraic number, permutation classes, Mathematics, combinatorial specification, Mathematics::Combinatorics, Generating function, random generation, Basis (universal algebra), [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Combinatorics (math.CO), MathematicsofComputing_DISCRETEMATHEMATICS |
| الوصف: | 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. Cet article présente une méthodologie qui calcule automatiquement une spécification combinatoire pour la classe de permutations $\mathcal{C} = Av(B)$, étant donnés une base $B$ de motifs interdits et l’ensemble des permutations simples de $\mathcal{C}$, lorsque ces deux ensembles sont finis. Ce résultat est obtenu en considérant à la fois des contraintes de motifs interdits et de motifs obligatoires dans les permutations. La spécification obtenue donne un système d’équations satisfait par la série génératrice de la classe $\mathcal{C}$, système qui est toujours positif et algébrique. Elle fournit aussi un générateur aléatoire uniforme de permutations dans $\mathcal{C}$. La méthode présentée est complètement algorithmique. |
| وصف الملف: | application/pdf |
| تدمد: | 1462-7264 1365-8050 |
| DOI: | 10.46298/dmtcs.3082⟩ |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2dd2dfcbf94227a571b18dc6bcaf8887 https://hal-upec-upem.archives-ouvertes.fr/hal-00685023 |
| Rights: | OPEN |
| رقم الانضمام: | edsair.doi.dedup.....2dd2dfcbf94227a571b18dc6bcaf8887 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 14627264 13658050 |
|---|---|
| DOI: | 10.46298/dmtcs.3082⟩ |