Decidability results for weighted-language equivalence via bisimulation up-to

Speaker(s)

Joost Winter

Affiliation

Uniwersytet Warszawski

Date

May 18, 2016, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

In this talk, I will present work earlier presented at FoSSaCS 2015, showing how the bisimulation-up to technique, the decidablity of weighted language equivalence for Noetherian semirings (originally proven by Ésik and Maletti) can be obtained using -almost- purely categorical methods, using the technique of lambda-bisimulation (or bisimulation up-to context). This proof is in principle more general than Ésik and Maletti's original proof, as it is given on the level of distributive laws of monads over endofunctors, allowing for instantiations beyond weighted automata, on the level of distributive laws of monads over endofunctors (on Set) satisfying suitable conditions.

---