Syntactic Monoids and Their Dual

Because of the isomorphism (X 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. In this talk, we will discuss deterministic automata as an elementary and typical example for the combined use of algebraic and coalgebraic methods in computer science. The algebra-coalgebra duality of automata will, more specifically, serve as a common perspective for the study of both varieties and covarieties, which are classes of automata and languages defined by equations and coequations, respectively. Along the way, we will establish a first connection with Eilenberg's definition of varieties of languages, which is based on the classical, algebraic notion of varieties of (transition) monoids. This is joint work with Adolfo Ballester-Bolinches and Enric Cosme-Llopez (University of Valencia).  

hosted by