Automata and coinduction (an exercise in coalgebra). (English) Zbl 0940.68085

Rutten, J. J. M. M.

Sangiorgi, Davide (ed.) et al., CONCUR ’98. Concurrency theory. 9th international conference, Nice, France, September 8-11, 1998. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1466, 194-218 (1998).

Summary: The classical theory of deterministic automata is presented in terms of the notions of homomorphism and bisimulation, which are the cornerstones of the theory of (universal) coalgebra. This leads to a transparent and uniform presentation of automata theory and yields some new insights, amongst which coinduction proof methods for language equality and language inclusion. At the same time, the present treatment of automata theory may serve as an introduction to coalgebra.
For the entire collection see [Zbl 0895.00051].

MSC:

68Q70

Algebraic theory of languages and automata

Keywords:

deterministic automata; bisimulation