On the intersection of stacks and queues (Q1123639)

The author establishes numerous strict inclusions and incomparabilities between the families of one-reversal one-counter, restricted one-counter, one-counter, linear context-free, single-reset, context-free, and queue languages, and various intersections of them. In fact, fourteen families are involved in a lattice presented in the paper. We mention some of the results. By a clever choice of bounded languages it is shown that (1) \({\mathcal M}(PAL)\cap {\mathcal M}(COPY)\) contains a language not in \({\mathcal M}(C)\) where \(C=(D_ 1c)^*\); (2) \({\mathcal M}(PAL)\cap {\mathcal M}(D_ 1)\) contains a language not in \({\mathcal M}(COPY)\); (3) \({\mathcal M}(COPY)\cap {\mathcal M}(D_ 1)\) contains a language not in \({\mathcal M}(PAL)\); (4) \({\mathcal M}(S)\) is strictly included in \({\mathcal M}(PAL)\cap {\mathcal M}(COPY)\cap {\mathcal M}(D_ 1)\) where S consists of all words \(a^ nb^ n\). These results disprove conjectures presented by several authors about ten years ago.