6533b7d4fe1ef96bd12627ed

RESEARCH PRODUCT

The dual equivalence of equations and coequations for automata

subject

description

The transition structure α : X ? X A of a deterministic automaton with state set X and with inputs from an alphabet A can be viewed both as an algebra and as a coalgebra. We use this algebra-coalgebra duality as a common perspective for the study of equations and coequations. For every automaton ( X , α ) , we define two new automata: free ( X , α ) and cofree ( X , α ) representing, respectively, the greatest set of equations and the smallest set of coequations satisfied by ( X , α ) . Both constructions are shown to be functorial. Our main result is that the restrictions of free and cofree to, respectively, preformations of languages and to quotients A * / C of A * with respect to a congruence relation C, form a dual equivalence. As a consequence, we present a variant of Eilenberg's celebrated variety theorem for varieties of monoids (in the sense of Birkhoff) and varieties of languages.