2026-03-17
The Queue Automaton Revisited
Publication
Publication
We consider the computational model of the Queue Automaton. An old result is that the deterministic queue automaton is equally expressive as the Turing machine. In a previous paper, we introduced the Reactive Turing Machine, enhancing the Turing machine with a notion of interaction. The Reactive Turing Machine defines all executable processes. In this paper, we prove that the non-deterministic queue automaton is equally expressive as the Reactive Turing Machine. Together with finite automata, pushdown automata and parallel pushdown automata, queue automata form a nice hierarchy of executable processes, with stacks, bags and queues as central elements.
| Additional Metadata | |
|---|---|
| doi.org/10.1007/978-3-032-20684-8_2 | |
| Lecture Notes in Computer Science | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Baeten, J., & Luttik, B. (2026). The Queue Automaton Revisited. Juggling Formal Methods and Security: Essays Dedicated to Sjouke Mauw on the Occasion of His 65th Birthday, 8–28. doi:10.1007/978-3-032-20684-8_2 |
|
