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

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

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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download

https://hal-polytechnique.archives-ouvertes.fr/hal-00458295
Contributor : Frédérique Bassino Connect in order to contact the contributor
Submitted on : Friday, March 4, 2011 - 6:08:54 PM
Last modification on : Wednesday, January 19, 2022 - 4:42:04 PM
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

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⟩

Share

Metrics

Record views

663

Files downloads

142