## Contact

Swiss National Science Foundation (SNSF)

Wildhainweg 3P.O. Box

CH-3001 Bern

Phone +41 31 308 22 22

Type of publication | Peer-reviewed |
---|---|

Publikationsform | Original article (peer-reviewed) |

Author | Frédérique Bassino, Mathilde Bouvel, Adeline Pierrot, Dominique Rossin, |

Project | Permutation classes: from structure to combinatorial properties |

Journal | Advances in Applied Mathematics |
---|---|

Volume (Issue) | 64 |

Page(s) | 124 - 200 |

Title of proceedings | Advances in Applied Mathematics |

URL | http://arxiv.org/abs/1307.2006 |
---|---|

Type of Open Access | Repository (Green Open Access) |

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.

Swiss National Science Foundation (SNSF)

Wildhainweg 3P.O. Box

CH-3001 Bern

Phone +41 31 308 22 22

Enter and manage your applications

Enter your e-mail address to receive the SNSF Newsletter regularly

© SNSF 2018