0000000000234187
AUTHOR
Jan Rutten
The dual equivalence of equations and coequations for automata
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 congr…
Formations of Monoids, Congruences, and Formal Languages
The main goal in this paper is to use a dual equivalence in automata theory started in [25] and developed in [3] to prove a general version of the Eilenberg-type theorem presented in [4]. Our principal results confirm the existence of a bijective correspondence between three concepts; formations of monoids, formations of languages and formations of congruences. The result does not require finiteness on monoids, nor regularity on languages nor finite index conditions on congruences. We relate our work to other results in the field and we include applications to non-r-disjunctive languages, Reiterman s equational description of pseudovarieties and varieties of monoids.
Varieties and Covarieties of Languages (Extended Abstract)
AbstractBecause of the isomorphism (X×A)→X≅X→(A→X), the transition structure 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. This algebra-coalgebra duality goes back to Arbib and Manes, who formulated it as a duality between reachability and observability, and is ultimately based on Kalmanʼs duality in systems theory between controllability and observability. Recently, it was used to give a new proof of Brzozowskiʼs minimization algorithm for deterministic automata. Here we will use the algebra-coalgebra duality of automata as a common perspective for the study of both varieties and covarieties, which are …