3 May 2005 2:30 - 4:00 Jan Rutten (CWI and VUA, Amsterdam) Algebraic specification and coalgebraic synthesis of sequential machines Abstract: This talk illustrates the usefulness of identifying (existing) mathematical structures as having a universal categorical property. (i) In particular, we briefly review that deterministic automata, and the sets of rational expressions and formal languages are all coalgebras, the latter being final. The benefit obtained from this perspective adds to the classical theory of automata a new coinductive proof principle for language equivalence. (Most of this goes back to the early 70's, the coinduction bit is from the late 90's). (ii) The main subject of the talk deals with a similar programme, but now for the class of so-called sequential machines. It is well-known that these are coalgebras. An elementary (and new) observation is that the set of causal functions from input streams to output streams is a final coalgebra. Its coalgebra structure leads to the definition of a new `derivative' operation for causal stream functions (generalising Brzozowski's input derivative for rational expressions from 1964). This so-called `functional stream derivative' leads to a new and efficient algortihm for the synthesis of minimal sequential machines. As a concrete application, we shall briefly discuss how to obtain minimal machines (and therewith memory-minimal digital circuits) from bitstream functions specified in the algebra of the 2-adic numbers.