Simple permutations: Decidability and unavoidable substructures

Brignall, Robert; Ruškuc, Nik and Vatter, Vincent (2008). Simple permutations: Decidability and unavoidable substructures. Theoretical Computer Science, 391(1-2) pp. 150–163.

DOI: https://doi.org/10.1016/j.tcs.2007.10.037

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.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 23471
• Item Type
• Journal Item
• ISSN
• 0304-3975
• Keywords
• permutation class; restricted permutation; simple permutation
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2007 Elsevier B.V
• Depositing User
• Robert Brignall