An algorithm computing combinatorial specifications of permutation classes

Frédérique Bassino; Mathilde Bouvel; Adeline Pierrot; Carine Pivoteau; Dominique Rossin

doi:10.1016/j.dam.2017.02.013

An algorithm computing combinatorial specifications of permutation classes

Frédérique Bassino ¹ Mathilde Bouvel ² Adeline Pierrot ^{3, 4} Carine Pivoteau ⁵ Dominique Rossin ⁶

1 LIPN - Laboratoire d'Informatique de Paris-Nord

2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

3 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications

4 BioInfo - LRI - Bioinformatique (LRI)

LRI - Laboratoire de Recherche en Informatique

5 LIGM - Laboratoire d'Informatique Gaspard-Monge

6 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]

Abstract : This article presents a methodology that automatically derives a combinatorial specification for a permutation class C, given its basis B of excluded patterns and the set of simple permutations in 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 C, this system being always positive and algebraic. It also yields a uniform random sampler of permutations in C. The method presented is fully algorithmic.

Type de document :

Article dans une revue

Discrete Applied Mathematics, Elsevier, 2017, 224, pp.16-44. 〈10.1016/j.dam.2017.02.013〉

Domaine :

Mathématiques [math] / Combinatoire [math.CO]

Liste complète des métadonnées

https://hal-upec-upem.archives-ouvertes.fr/hal-01175234
Contributeur : Carine Pivoteau <>
Soumis le : vendredi 10 juillet 2015 - 13:45:46
Dernière modification le : jeudi 7 février 2019 - 14:52:38

An algorithm computing combinatorial specifications of permutation classes

Lien texte intégral

Identifiants

Collections

Citation

Exporter

Métriques

586

Contact

An algorithm computing combinatorial specifications of permutation classes

Lien texte intégral

Identifiants

Collections

Citation

Exporter

Partager

Métriques

586

Contact