IFIP Logo
Sign in for Members and Observers

IFIP WG1.3 Foundations of System Specification


Talk "Uniform Eilenberg Theorem: Syntactic Algebras For Free"

by Stefan Milius

Tue, 02 September 2014 at 11:00 am in Sinaia, Romania

Joint work with: Jiri Adamek, Rob Myers, Henning Urbat

Abstract: We investigate the duality between algebraic and coalgebraic recognition of languages to derive a generalization of the version of Eilenberg’s theorem. This theorem states that the lattice of all boolean algebras of regular languages closed under derivatives and preimages of homomorphisms is isomorphic to the lattice of all pseudovarieties monoids. By applying our method to different categories, we obtain several previously known and also new Eilenberg-type theorems as special instances. And we also have uniform proofs for local versions of Eilenberg-type theorems, e.g. one due to Gehrke, Grigorieff and Pin, weakens boolean algebras to distributive lattices, one due to Polák weakens them to join-semilattices, and the last one considers vector spaces over Z_2.

Slides