Simple permutations: decidability and unavoidable substructures

RLF Brignall, N Ruskuc, V Vatter

Research output: Contribution to journalArticle (Academic Journal)peer-review

20 Citations (Scopus)


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 contributionSimple permutations: decidability and unavoidable substructures
Original languageEnglish
Pages (from-to)150 - 163
Number of pages13
JournalTheoretical Computer Science
Volume391, issues 1 &2
Publication statusPublished - Feb 2008

Bibliographical note

Publisher: Elsevier BV


Dive into the research topics of 'Simple permutations: decidability and unavoidable substructures'. Together they form a unique fingerprint.

Cite this