Pattern avoiding permutations are context-sensitive

2004/12/01 by Murray Elder, Elder, Murray
Mathematics · #03D10 #05A05 #68Q45 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:03D10 #msc:05A05 #msc:68Q45

paper · pdf · doi:10.48550/arxiv.math/0412019

arxiv created 2005/03/28 · arxiv updated 2009/12/01

Abstract

We establish a bijection from the set of all permutations (of a given length) that avoid a pattern q and a context-sensitive language.

Related

• Pattern avoidance in compositions and powers of permutations
• Generalised Pattern Avoidance
• Flexible Schemes for Pattern-Avoiding Permutations
• Powers of permutations that avoid chains of patterns
• On the enumeration of permutations avoiding chains of patterns