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 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

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

1058

Files downloads

218