HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

An algorithm computing combinatorial specifications of permutation classes

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.
Document type :
Journal articles
Complete list of metadata

https://hal-upec-upem.archives-ouvertes.fr/hal-01175234
Contributor : Carine Pivoteau Connect in order to contact the contributor
Submitted on : Friday, July 10, 2015 - 1:45:46 PM
Last modification on : Wednesday, January 19, 2022 - 4:42:04 PM

Links full text

Identifiers

Citation

Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot, Carine Pivoteau, Dominique Rossin. An algorithm computing combinatorial specifications of permutation classes. Discrete Applied Mathematics, Elsevier, 2017, 224, pp.16-44. ⟨10.1016/j.dam.2017.02.013⟩. ⟨hal-01175234⟩

Share

Metrics

Record views

364