Determinization constructions: from automata to coalgebras

The powerset construction is a standard method for converting a nondeterministic automaton into an equivalent deterministic one as far as language is concerned. In this talk, we lift the powerset construction on automata to the more general framework of coalgebras with structured state spaces. Examples of applications include partial Mealy machines, (structured) Moore automata, and Rabin probabilistic automata. A somewhat surprising outcome of our framework, which I will show if time allows, is the first coalgebraic characterisation of pushdown automata, a long standing open question in the coalgebraic community. The talk will be example-driven! This is happy joint work with BBR: Bonchi, Bonsangue and Rutten.  

hosted by