Collapsible Pushdown Systems

I will briefly describe two results (the second one is a joint work with A. Kartzow). One is that collapsible pushdown systems are more expressible that higher-order pushdown systems without collapse, for any level. This extends my previously presented work which was for level 2 only. The second result is that the hierarchy of trees (and the hierarchy of graphs) generated by collapsible pushdown systems is strict, i.e. different for each level. Both results are obtained by proving and using some "pumping lemmas".

Let us remind that an n-th level pushdown automaton is a pushdown automaton, which has a stack of stacks of ... of stacks. It works like a normal pushdown automaton, seeing only the topmost sybmol on the topmost stack, but it can also copy a stack of some level, or remove a stack of some level. Sometimes an additional operation called "collapse" is allowed; then we obtain collapsible automata.