A Process-Theoretic Look at Automata
J. C. M. Baeten, Pjl Pieter Cuijpers, Bas Luttik, P. J. A. van Tilburg · 2009
Abstract. Automata theory presents roughly three types of automata: finite automata, pushdown automata and Turing machines. The au-tomata are treated as language acceptors, and the expressiveness of the automata models are considered modulo language equivalence. This no-tion of equivalence is arguably too coarse to satisfactorily deal with a notion of interaction that is fundamental to contemporary computing. In this paper we therefore reconsider the automaton models from au-tomata theory modulo branching bisimilarity, a well-known behavioral equivalence from process theory that has proved to be able to satisfacto-rily deal with interaction. We investigate to what extent some standard results from automata theory are still valid if branching bisimilarity is adopted as the preferred equivalence. 1