Pattern avoiding permutations are context-sensitive

Murray Elder (University of St Andrews, Scotland)

Abstract: In this talk we will consider a connection between pattern avoiding permutations and formal language theory. We will construct a bijection from the set of permutations which avoid a fixed pattern q and a language of strings over a finite alphabet that is context-sensitive. It may be that one can improve this result to a more restricted language class, such as indexed, and one might hope that the formal language information could lead to a nice generating function for the set, in analogy with the fact that context-free languages have algebraic generating functions and regular languages have rational ones.

Algebraic Combinatorics Seminar home