Simple permutations: decidability and unavoidable substructures

RLF Brignall; N Ruskuc; V Vatter

doi:10.1016/j.tcs.2007.10.037

Simple permutations: decidability and unavoidable substructures

RLF Brignall, N Ruskuc, V Vatter

School of Mathematics

Research output: Contribution to journal › Article (Academic Journal) › peer-review

22 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 contribution	Simple permutations: decidability and unavoidable substructures
Original language	English
Pages (from-to)	150 - 163
Number of pages	13
Journal	Theoretical Computer Science
Volume	391, issues 1 &2
DOIs	https://doi.org/10.1016/j.tcs.2007.10.037
Publication status	Published - Feb 2008

Bibliographical note

Publisher: Elsevier BV

Access to Document

10.1016/j.tcs.2007.10.037

Handle.net

Persistent link

Cite this

@article{22ad7e17b2af41cba801993f903a4e08,

title = "Simple permutations: decidability and unavoidable substructures",

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.",

author = "RLF Brignall and N Ruskuc and V Vatter",

note = "Publisher: Elsevier BV",

year = "2008",

month = feb,

doi = "10.1016/j.tcs.2007.10.037",

language = "English",

volume = "391, issues 1 &2",

pages = "150 -- 163",

journal = "Theoretical Computer Science",

publisher = "Amsterdam:Elsevier",

}

TY - JOUR

T1 - Simple permutations: decidability and unavoidable substructures

AU - Brignall, RLF

AU - Ruskuc, N

AU - Vatter, V

N1 - Publisher: Elsevier BV

PY - 2008/2

Y1 - 2008/2

N2 - 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.

AB - 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.

U2 - 10.1016/j.tcs.2007.10.037

DO - 10.1016/j.tcs.2007.10.037

M3 - Article (Academic Journal)

VL - 391, issues 1 &2

SP - 150

EP - 163

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Simple permutations: decidability and unavoidable substructures

Abstract

Bibliographical note

Access to Document

Handle.net

Fingerprint

Cite this