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.

  • 4
    $\begingroup$ You mean this? https://en.wikipedia.org/wiki/Queue_automaton $\endgroup$ – Logan Mayfield Aug 22 '15 at 16:33
  • 1
    $\begingroup$ Quite embarrassing I managed to miss that, but yes that's exactly what I meant. Thanks for pointing it out. $\endgroup$ – Fasermaler Aug 23 '15 at 6:30
  • $\begingroup$ I think queue automata are pretty interesting. If you have any neat variations or restricted classes of queue automata, do share. :) $\endgroup$ – Michael Wehar Aug 26 '15 at 17:19
  • 1
    $\begingroup$ @Fasermaler Take a look at Multi-stack Pushdown Automata with bounded phase switches. Also look at this paper: ideals.illinois.edu/bitstream/handle/2142/15433/… $\endgroup$ – Michael Wehar Sep 1 '15 at 0:30
  • 1
    $\begingroup$ @MichaelWehar Thanks a lot for that paper. I reckon it'll take a while for me to fully absorb it, but I happen to be looking into treewidth at the moment, so this is very interesting stuff! $\endgroup$ – Fasermaler Sep 1 '15 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.