Collections | Livre | Chapitre
A bialgebraic review of deterministic automata, regular expressions and languages
pp. 375-404
Résumé
This papers reviews the classical theory of deterministic automata and regular languages from a categorical perspective. The basis is formed by Rutten's description of the Brzozowski automaton structure in a coalgebraic framework. We enlarge the framework to a so-called bialgebraic one, by including algebras together with suitable distributive laws connecting the algebraic and coalgebraic structure of regular expressions and languages. This culminates in a reformulated proof via finality of Kozen's completeness result. It yields a complete axiomatisation of observational equivalence (bisimilarity) on regular expressions. We suggest that this situation is paradigmatic for (theoretical) computer science as the study of "generated behaviour".
Détails de la publication
Publié dans:
Futatsugi Kokichi, Jouannaud Jean-Pierre, Meseguer José (2006) Algebra, meaning, and computation: essays dedicated to Joseph A. Goguen on the occasion of his 65th birthday. Dordrecht, Springer.
Pages: 375-404
DOI: 10.1007/11780274_20
Citation complète:
Jacobs Bart, 2006, A bialgebraic review of deterministic automata, regular expressions and languages. In K. Futatsugi, J. Jouannaud & J. Meseguer (eds.) Algebra, meaning, and computation (375-404). Dordrecht, Springer.