A while ago it occurred to me that the stack data model in a push-down automaton could be exchanged for a queue or deque model. I've explored this a bit as a pet project and it looks like an automaton with a deque model is TM equivalent. Intuitively because analogous to moving a head over a fixed tape, the deque model allows for moving the tape under a fixed head. Formally I think this could be proved nicely via equivalence with a dual stack PDA.The queue model continues to puzzle me however, since it seems to define a class of languages quite different from the context-free languages (stack vs. queue seems to be analogous to nested vs. cross-serial character dependencies). I haven't been able to prove or disprove whether the queue model also accepts context-free languages though, so it might just as well turn out to be TM equivalent too. On the other hand I also couldn't construct the equivalents of the TM transition relations using the queue model, it seems to fall just short of 'full TM power'.At this point I've started going in circles, so I'm left with the question whether the queue model would really define a separate (not necessarily useful) class of languages or not. It seems a simple question but I haven't been able to find any conclusive literature on this, so I was hoping someone could point me to an answer to this question.
What would a PDA be with a queue instead of a stack?
reference request;automata theory;turing machines