<p>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.</p>

<p>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'.</p>

<p>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.</p>

CC BY-SA 3.0
2015-08-22T16:33:34.923Z
You mean this? [https://en.wikipedia.org/wiki/Queue_automaton](https://en.wikipedia.org/wiki/Queue_automaton)
Logan Mayfield
CC BY-SA 3.0
2015-08-23T06:30:58.173Z
Quite embarrassing I managed to miss that, but yes that's exactly what I meant. Thanks for pointing it out.
Fasermaler
CC BY-SA 3.0
2015-08-26T17:19:00.350Z
I think queue automata are pretty interesting.  If you have any neat variations or restricted classes of queue automata, do share.  :)
Michael Wehar
CC BY-SA 3.0
2015-08-27T15:27:50.013Z
@MichaelWehar Thanks for your interest, unfortunately I don't think I have any neat stuff to share really. I started toying with this from the wrong assumption that languages accepted by queue automata might be a subset of SD, so my work is quite structurally flawed. I did spend some time tinkering on a deque variant (not linear bounded, so TM equivalent) and some vague notions about a hybrid PDA/Queue automaton (without restrictions, so also TM equivalent). If nothing else, I learned it's surprisingly hard to come up with anything that isn't TM equivalent :)
Fasermaler
CC BY-SA 3.0
2015-09-01T00:28:12.470Z
@Fasermaler Thanks for your response!  Keep at it.  There are a lot of multi-stack pushdown automata variants that are **not** TM equivalent.  A standard two stack automata is TM equivalent, but if you bound the number of times you can switch between which stack you can pop from, then it's not TM equivalent.  :)
Michael Wehar
CC BY-SA 3.0
2015-09-01T00:30:30.100Z
@Fasermaler Take a look at Multi-stack Pushdown Automata with bounded phase switches.  Also look at this paper: https://www.ideals.illinois.edu/bitstream/handle/2142/15433/graphautomata-tr.pdf?sequence=2
Michael Wehar
CC BY-SA 3.0
2015-09-01T00:31:39.483Z
@Fasermaler I once had the thought that there could be interesting variations of Multi-Queue Automata with a decidable halting problem.  And, possibly also decidable non-emptiness and equivalence problems.  :)
Michael Wehar
CC BY-SA 3.0
2015-09-01T09:02:07.950Z
@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!
Fasermaler
CC BY-SA 3.0
2015-09-06T15:20:57.400Z
@Fasermaler Sure, no problem.  Cool!  :)
Michael Wehar
CC BY-SA 4.0
2020-11-04T08:09:32.347Z
Please help here (https://or.stackexchange.com/questions/5147/is-optimal-solution-to-dual-not-unique-if-optimal-solution-to-the-primal-is-dege) in re here (https://math.stackexchange.com/questions/1095760/is-optimal-solution-to-dual-not-unique-if-optimal-solution-to-the-primal-is-dege)
BCLC
<reference-request><automata-theory><turing-machines>
What would a PDA be with a queue instead of a stack?
Fasermaler
# What would a PDA be with a queue instead of a stack?

(Asked by: username_0 on 2015-08-22)

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.

**Tags:** reference-request, automata-theory, turing-machines

> **Comments:**
> **username_1**: You mean this? [https://en.wikipedia.org/wiki/Queue_automaton](https://en.wikipedia.org/wiki/Queue_automaton)  
> **username_0**: Quite embarrassing I managed to miss that, but yes that's exactly what I meant. Thanks for pointing it out.  
> **username_2**: I think queue automata are pretty interesting.  If you have any neat variations or restricted classes of queue automata, do share.  :)  
> **username_0**: @MichaelWehar Thanks for your interest, unfortunately I don't think I have any neat stuff to share really. I started toying with this from the wrong assumption that languages accepted by queue automata might be a subset of SD, so my work is quite structurally flawed. I did spend some time tinkering on a deque variant (not linear bounded, so TM equivalent) and some vague notions about a hybrid PDA/Queue automaton (without restrictions, so also TM equivalent). If nothing else, I learned it's surprisingly hard to come up with anything that isn't TM equivalent :)  
> **username_2**: @username_0 Thanks for your response!  Keep at it.  There are a lot of multi-stack pushdown automata variants that are **not** TM equivalent.  A standard two stack automata is TM equivalent, but if you bound the number of times you can switch between which stack you can pop from, then it's not TM equivalent.  :)  
> **username_2**: @username_0 Take a look at Multi-stack Pushdown Automata with bounded phase switches.  Also look at this paper: https://www.ideals.illinois.edu/bitstream/handle/2142/15433/graphautomata-tr.pdf?sequence=2  
> **username_2**: @username_0 I once had the thought that there could be interesting variations of Multi-Queue Automata with a decidable halting problem.  And, possibly also decidable non-emptiness and equivalence problems.  :)  
> **username_0**: @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!  
> **username_2**: @username_0 Sure, no problem.  Cool!  :)  
> **username_3**: Please help here (https://or.stackexchange.com/questions/5147/is-optimal-solution-to-dual-not-unique-if-optimal-solution-to-the-primal-is-dege) in re here (https://math.stackexchange.com/questions/1095760/is-optimal-solution-to-dual-not-unique-if-optimal-solution-to-the-primal-is-dege)  

---

## 0 answers

