Simple permutations: decidability and unavoidable substructures

RLF Brignall, N Ruskuc, V Vatter

Research output: Contribution to journalArticle (Academic Journal)

18 Citations (Scopus)

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.
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
DOIs
Publication statusPublished - Feb 2008

Bibliographical note

Publisher: Elsevier BV

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

  • Cite this