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.