CoPaR: An Efficient Generic Partition Refiner
share
Partition refinement is a method for minimizing automata and transition systems of various types. We present a tool implementing a recently developed partition refinement algorithm that is generic in the transition type of the given system and typically runs in time either O(m· n) or O(m· n· m) for systems with m edges and n states. This matches the runtime of the best known algorithms for several fixed types of systems, e.g. deterministic automata as well as ordinary, weighted, and probabilistic (labelled) transition systems, and in the case of weighted systems over non-cancellative monoids, such as (the additive monoid of) the tropical semiring, even improves the asymptotic runtime. Genericity is achieved by modelling transition types as endofunctors on sets and state-based systems as coalgebras. In addition to thus obtaining an efficient partion refiner for the mentioned types of systems, we demonstrate how the user can quickly obtain a partition refiner for new types of systems by composing pre-implemented basic functors, and how the tool can easily be extended with new basic functors by implementing a refinement interface.
READ FULL TEXT