Sorting with C-machines
Abstract.
A C-machine is a type of sorting device that naturally generalizes
stacks and queues. A C-machine is a container that is allowed to hold
permutations from the class C into which entries can be pushed and out
of which entries may be popped. With this notation, a traditional
stack is the Av(12)-machine. This structural description allows us
to find many terms in the counting sequences of several permutation
classes of interest, but despite these numerous initial terms we are
unable to find the exact or asymptotic behavior of their generating
functions. I'll discuss what we do know, what we don't know, and what
experimental methods tell us we might one day know.