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

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

Recommendations