Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial

Frédérique Bassino 1, * Mathilde Bouvel 2, * Adeline Pierrot 3, * Dominique Rossin 4, *
* Corresponding author
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 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : We present an algorithm running in time O(n ln n) which decides if a wreath-closed permutation class Av(B) given by its finite basis B contains a finite number of simple permutations. The method we use is based on an article of Brignall, Ruskuc and Vatter which presents a decision procedure (of high complexity) for solving this question, without the assumption that Av(B) is wreath-closed. Using combinatorial, algorithmic and language theoretic arguments together with one of our previous results on pin-permutations, we are able to transform the problem into a co-finiteness problem in a complete deterministic automaton.
Document type :
Journal articles
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download
https://hal-polytechnique.archives-ouvertes.fr/hal-00458295
Contributor : Frédérique Bassino <>
Submitted on : Friday, March 4, 2011 - 6:08:54 PM
Last modification on : Tuesday, April 2, 2019 - 1:45:31 AM
Long-term archiving on: Sunday, June 5, 2011 - 3:00:00 AM

Files

PuMA.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00458295, version 3
  • ARXIV : 1002.3866

Collections

CNRS | LIX | PARISTECH | X-LIX | X | INSMI | UNIV-PARIS7 | LIX_EMC | UNIV-PARIS13 | LIPN | LABRI | USPC | X-DEP-INFO | GALILE | UNIV-BORDEAUX

Citation

Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot, Dominique Rossin. Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial. Pure Mathematics and Applications, 2010, 21 (2), pp.119-135. ⟨hal-00458295v3⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

1062

Files downloads

223

Contact

Informations

CCSD