Linguistique de l’écrit

Revue internationale en libre accès

Collections | Livre | Chapitre

225402

A bialgebraic review of deterministic automata, regular expressions and languages

Bart Jacobs

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.