Skip to Main content Skip to Navigation
Conference papers

Combinatorial specification of permutation classes

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00685023
Contributor : Carine Pivoteau Connect in order to contact the contributor
Submitted on : Tuesday, April 3, 2012 - 5:14:41 PM
Last modification on : Thursday, October 21, 2021 - 10:44:08 AM
Long-term archiving on: : Wednesday, December 14, 2016 - 7:51:13 PM

Files

fpsac_final.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00685023, version 1
  • ARXIV : 1204.0797
`

Citation

Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot, Carine Pivoteau, Dominique Rossin. Combinatorial specification of permutation classes. 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), Jul 2012, Nagoya, Japan. pp.781 - 792. ⟨hal-00685023⟩

Share

Metrics

Record views

927

Files downloads

796