Jos Baeten: The Queue Automaton: a Computational Model Equally Expressive as the (Reactive) Turing Machine


Event Details


We introduce a new computational model: the Queue Automaton. This computational model is
equally expressive as the Reactive Turing Machine. Thus, a process is executable if and only if it
is the process of a Queue Automaton, and a language is computable if and only if it is the language
of a Queue Automaton. Together with finite automata, pushdown automata and parallel pushdown
automata, we get a nice hierarchy of executable processes, with counters, stacks, bags and queues as
central elements.