哲学杂志철학 학술지哲学のジャーナルEast Asian
Journal of
Philosophy

Home > Book Series > Edited Book > Contribution

Publication details

Publisher: Springer

Place: Berlin

Year: 2006

Pages: 375-404

Series: Lecture Notes in Computer Science

ISBN (Hardback): 9783540354628

Full citation:

Bart Jacobs, "A bialgebraic review of deterministic automata, regular expressions and languages", in: Algebra, meaning, and computation, Berlin, Springer, 2006

A bialgebraic review of deterministic automata, regular expressions and languages

Bart Jacobs

pp. 375-404

in: Kokichi Futatsugi, Jean-Pierre Jouannaud, José Meseguer (eds), Algebra, meaning, and computation, Berlin, Springer, 2006

Abstract

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".

Publication details

Publisher: Springer

Place: Berlin

Year: 2006

Pages: 375-404

Series: Lecture Notes in Computer Science

ISBN (Hardback): 9783540354628

Full citation:

Bart Jacobs, "A bialgebraic review of deterministic automata, regular expressions and languages", in: Algebra, meaning, and computation, Berlin, Springer, 2006