 |
HAL UPEC - UPEM Portal |  |
 |
An algorithm computing combinatorial specifications of permutation classes
Frédérique Bassino 1
Mail : Site :
Author
Mathilde Bouvel 2
Mail :
Author
Adeline Pierrot 3, 4
Mail :
Author
Carine Pivoteau 5
Mail :
Author IdHAL : carine-pivoteau
Dominique Rossin 6
Mail : Site :
Author IdHAL : dominique-rossin
1
LIPN - Laboratoire d'Informatique de Paris-Nord (Institut Galilée, Université Paris 13, 99 avenue Jean-Baptiste Clément, F-93430, Villetaneuse - France)
- USPC - Université Sorbonne Paris Cité (Université Sorbonne Paris Cité | 100-104, avenue de France | 75013 Paris - France)
- Institut Galilée (France)
- UP13 - Université Paris 13 (France)
- CNRS - Centre National de la Recherche Scientifique : UMR7030 (France)
2
LaBRI - Laboratoire Bordelais de Recherche en Informatique (Domaine Universitaire 351, cours de la Libération 33405 Talence Cedex - France)
- CNRS - Centre National de la Recherche Scientifique : UMR5800 (France)
- École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) (France)
- Université Sciences et Technologies - Bordeaux 1 (351 cours de la Libération - 33405 Talence cedex - France)
- Université Bordeaux Segalen - Bordeaux 2 (146 rue Léo Saignat - 33076 Bordeaux cedex - France)
3
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications (Université Paris Diderot, Bât. Sophie Germain, case postale 7014, 75205 Paris cedex 13 - France)
- CNRS - Centre National de la Recherche Scientifique : UMR7089 (France)
- UPD7 - Université Paris Diderot - Paris 7 (5 rue Thomas-Mann - 75205 Paris cedex 13 - France)
4
BioInfo - LRI - Bioinformatique (LRI) (Université Paris Sud
Bât. 650 Lovelace
91405 Orsay Cedex - France)
- LRI - Laboratoire de Recherche en Informatique (LRI - Bâtiments 650-660 Université Paris-Sud 91405 Orsay Cedex - France)
- UP11 - Université Paris-Sud - Paris 11 (Bâtiment 300 - 91405 Orsay cedex - France)
- CentraleSupélec (3, rue Joliot Curie, Plateau de Moulon, 91192 GIF-SUR-YVETTE Cedex - France)
- CNRS - Centre National de la Recherche Scientifique : UMR8623 (France)
5
ligm - Laboratoire d'Informatique Gaspard-Monge (Université de Paris-Est Marne-la-Vallée, Cité Descartes, Bâtiment Copernic, 5 bd Descartes, 77454 Marne-la-Vallée Cedex 2 - France)
- UPEM - Université Paris-Est Marne-la-Vallée (5 boulevard Descartes - Champs-sur-Marne - 77454 Marne-la-Vallée Cedex 2 - France)
- ENPC - École des Ponts ParisTech (École des Ponts ParisTech 6-8 avenue Blaise-Pascal Cité Descartes 77455 Champs-sur-Marne Marne-la-Vallée cedex 2 - France)
- ESIEE Paris (2 boulevard Blaise Pascal Cité Descartes BP 99 93162 Noisy-le-Grand Cedex - France)
- Fédération de Recherche Bézout (France)
- CNRS - Centre National de la Recherche Scientifique : UMR8049 (France)
6
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau] (Route de Saclay 91128 PALAISEAU CEDEX - France)
- CNRS - Centre National de la Recherche Scientifique : UMR7161 (France)
- X - École polytechnique (École polytechnique, 91128 Palaiseau Cedex - France)
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
Domain :
Complete list of metadatas
https://hal-upec-upem.archives-ouvertes.fr/hal-01175234
Contributor : Carine Pivoteau <>
Submitted on : Friday, July 10, 2015 - 1:45:46 PM
Last modification on : Friday, March 27, 2020 - 3:30:45 AM
Contributor : Carine Pivoteau <>
Submitted on : Friday, July 10, 2015 - 1:45:46 PM
Last modification on : Friday, March 27, 2020 - 3:30:45 AM
Links full text
Identifiers
- HAL Id : hal-01175234, version 1
- ARXIV : 1506.00868
- DOI : 10.1016/j.dam.2017.02.013
Collections
UPEC-UPEM | ENPC | PARISTECH | CNRS | UNIV-PARIS7 | UNIV-PARIS13 | X | LIX | INSMI | X-LIX | LABRI | LIPN | LIGM_MOA | LIGM | USPC | UNIV-PARIS-SACLAY | UMR8623 | LRI-BIOINFO | CENTRALESUPELEC | X-DEP-INFO | ESIEE-PARIS | GALILE | UNIV-BORDEAUX
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⟩
Metrics
Record views
