pith. sign in

arxiv: 1002.3866 · v3 · pith:B2W3KGDPnew · submitted 2010-02-20 · 💻 cs.DS · math.CO

Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial

classification 💻 cs.DS math.CO
keywords wreath-closedclassfinitenumberpermutationsproblemsimpleable
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.