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

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

2010-02-20

arxiv.org/abs/1002.3866v3

Pure Mathematics and Applications 21, 2 (2010) 119-135

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deciding the finiteness of the number of simple permutations contained in a wreath-closed class is polynomial will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-692541