The Open UniversitySkip to content
 

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 (Digital Object Identifier) Link: http://dx.doi.org/10.1016/j.tcs.2007.10.037
Google Scholar: Look up in Google Scholar

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.

Item Type: Journal Article
Copyright Holders: 2007 Elsevier B.V
ISSN: 0304-3975
Keywords: permutation class; restricted permutation; simple permutation
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 23471
Depositing User: Robert Brignall
Date Deposited: 13 Oct 2010 15:51
Last Modified: 28 Feb 2012 15:42
URI: http://oro.open.ac.uk/id/eprint/23471
Share this page:

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk