Thu 15 March 2017, 16:30–18:00
ERATO MMSD Takebashi Site Common Room 3
http://group-mmm.org/eratommsd/access.html
Thorsten Wissman (FAU Erlangen-Nürnberg),
Efficient Coalgebraic Partition Refinement
This talk presents a generic partition refinement algorithm that quotients coalgebraic systems by behavioural equivalence. Coalgebraic generality implies in particular that not only classical relational systems are covered but also various forms of weighted systems. Under assumptions on the type functor that allow representing its finite coalgebras in terms of nodes and edges, the generic algorithm runs in time O(m⋅log n) where n and m are the numbers of nodes and edges, respectively. Instances of the generic algorithm thus match the runtime of the best known algorithms for unlabelled transition systems, Markov chains, and deterministic automata (with fixed alphabets), and improve the best known algorithms for Segala systems.