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/doi: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

Actions (login may be required)

	View Item
	Report issue / request change

Policies | Disclaimer