Simple permutations: decidability and unavoidable substructures

Robert Brignall; Nik Ruskuc; Vincent Vatter

doi:10.1016/j.tcs.2007.10.037

Simple permutations: decidability and unavoidable substructures

Robert Brignall, Nik Ruskuc, Vincent Vatter

Research output: Contribution to journal › Article › peer-review

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. (C) 2007 Elsevier B.V. All rights reserved.

Original language	English
Pages (from-to)	150-163
Number of pages	14
Journal	Theoretical Computer Science
Volume	391
Issue number	1-2
DOIs	https://doi.org/10.1016/j.tcs.2007.10.037
Publication status	Published - 4 Feb 2008

Keywords

permutation class
restricted permutation
simple permutation
RESTRICTED PERMUTATIONS
RELATIONAL STRUCTURES
CLOSED-SETS
TOURNAMENTS

Access to Document

10.1016/j.tcs.2007.10.037

Cite this

@article{292bef0f87fd41c3b68b4e24457641ba,

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. (C) 2007 Elsevier B.V. All rights reserved.",

keywords = "permutation class, restricted permutation, simple permutation, RESTRICTED PERMUTATIONS, RELATIONAL STRUCTURES, CLOSED-SETS, TOURNAMENTS",

author = "Robert Brignall and Nik Ruskuc and Vincent Vatter",

note = "Conference Information: International School and Conference on Combinatorics, Automata and Number Theory Univ Liege, Inst Math, Liege, Belgiom, May 08-19, 2006 ",

year = "2008",

month = feb,

day = "4",

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

language = "English",

volume = "391",

pages = "150--163",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier Science BV",

number = "1-2",

}

TY - JOUR

T1 - Simple permutations: decidability and unavoidable substructures

AU - Brignall, Robert

AU - Ruskuc, Nik

AU - Vatter, Vincent

N1 - Conference Information: International School and Conference on Combinatorics, Automata and Number Theory Univ Liege, Inst Math, Liege, Belgiom, May 08-19, 2006

PY - 2008/2/4

Y1 - 2008/2/4

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. (C) 2007 Elsevier B.V. All rights reserved.

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. (C) 2007 Elsevier B.V. All rights reserved.

KW - permutation class

KW - restricted permutation

KW - simple permutation

KW - RESTRICTED PERMUTATIONS

KW - RELATIONAL STRUCTURES

KW - CLOSED-SETS

KW - TOURNAMENTS

UR - http://www.scopus.com/inward/record.url?scp=38149051266&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2007.10.037

DO - 10.1016/j.tcs.2007.10.037

M3 - Article

SN - 0304-3975

VL - 391

SP - 150

EP - 163

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-2

ER -

Simple permutations: decidability and unavoidable substructures

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications

EPSRC GR/S53503/01: Applications of Automata and Languages in the Theory of Pattern Classes of Permutations

Cite this

Simple permutations: decidability and unavoidable substructures

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications

EPSRC GR/S53503/01: Applications of Automata and Languages in the Theory of Pattern Classes of Permutations

Cite this