An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
Authors:
Preprint
Abstract
In this article, we describe an algorithm to determine whether a permutation class C given by a finite basis B of excluded patterns contains a finite number of simple permutations. This is a continuation of the work initiated in [Brignall, Ruskuc, Vatter, Simple permutations: decidability and unavoidable substructures, 2008], and shares several aspects with it. Like in this article, the main difficulty is to decide whether C contains a finite number of proper pin-permutations, and this decision problem is solved using automata theory. Moreover, we use an encoding of proper pin-permutations by words over a finite alphabet, introduced by Brignall et al. However, unlike in their article, our construction of automata is fully algorithmic and efficient. It is based on the study of pin-permutations in [Bassino, Bouvel, Rossin, Enumeration of pin-permutations, 2011]. The complexity of the overall algorithm is O(n log n + s^{2k}) where n denotes the sum of the sizes of permutations in the basis B, s is the maximal size of a pin-permutation in B and k is the number of pin-permutations in B.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Combinatorial specification of permutation classesDiscrete Mathematics & Theoretical Computer Science, 2012
- AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALSDiscrete Mathematics, Algorithms and Applications, 2011
- Decomposing simple permutations, with enumerative consequencesCombinatorica, 2008
- Simple permutations and algebraic generating functionsJournal of Combinatorial Theory, Series A, 2008
- Simple permutations: Decidability and unavoidable substructuresTheoretical Computer Science, 2008
- Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of GraphsSIAM Journal on Discrete Mathematics, 2008
- Simple permutations and pattern restricted permutationsDiscrete Mathematics, 2005
- Algorithms for Pattern Involvement in Permutations2001
- Finding All Common Intervals of k Permutations2001
- Transitiv orientierbare GraphenActa Mathematica Hungarica, 1967