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

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

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

Domain :

Computer Science [cs] / Data Structures and Algorithms [cs.DS]

Mathematics [math] / Combinatorics [math.CO]

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

PuMA.pdf

Files produced by the author(s)

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

Files

Identifiers

Collections

Citation

Export

Metrics

1058

218

Contact

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

Files

Identifiers

Collections

Citation

Export

Share

Metrics

1058

218

Contact