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)

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]

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.

Domains: Computer Science [cs]; Data Structures and Algorithms [cs.DS]; Mathematics [math]; Combinatorics [math.CO]

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⟩