 |
École polytechnique Open archive |  |
 |
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.
Cited literature [13 references]
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
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)