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.
|Translated title of the contribution||Simple permutations: decidability and unavoidable substructures|
|Pages (from-to)||150 - 163|
|Number of pages||13|
|Journal||Theoretical Computer Science|
|Volume||391, issues 1 &2|
|Publication status||Published - Feb 2008|