Article ID Journal Published Year Pages File Type
435928 Theoretical Computer Science 2008 14 Pages PDF
Abstract

We prove that it is decidable whether a finitely based permutation class contains infinitely many simple permutations, and establish an unavoidable substructure result for simple permutations: every sufficiently long simple permutation contains an alternation or oscillation of length k.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics