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