کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4624684 | 1631632 | 2015 | 77 صفحه PDF | دانلود رایگان |
In this article, we describe an algorithm to determine whether a permutation class CC 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 [11], and shares several aspects with it. Like in this article, the main difficulty is to decide whether CC 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 [6]. The complexity of the overall algorithm is O(nlogn+s2k)O(nlogn+s2k) 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.
Journal: Advances in Applied Mathematics - Volume 64, March 2015, Pages 124–200