Recently, we have developed an efficient generic partition refinement algorithm, which computes behavioural equivalence on a state-based system given as an encoded coalgebra, and implemented it in the tool CoPaR. Here we extend this to a fully fledged minimization algorithm and tool by integrating two new aspects: (1) the computation of the transition structure on the minimized state set, and (2) the computation of the reachable part of the given system. In our generic coalgebraic setting these two aspects turn out to be surprisingly non-trivial requiring us to extend the previous theory. In particular, we identify a sufficient condition on encodings of coalgebras, and we show how to augment the existing interface, which encapsulates computations that are specific for the coalgebraic type functor, to make the above extensions possible. Both extensions have linear run time.
翻译:最近,我们开发了高效的通用分区精细算法,该算法计算了以国家为基础的系统上的行为等值,作为编码的煤子数,并在工具COPAR中应用。我们在此将这一算法扩大到一个完全成熟的最小化算法和工具,整合了两个新的方面:(1) 在最小状态集上计算过渡结构,(2) 计算特定系统的可达部分。在我们的通用的煤层精细算法中,这两个方面是令人惊讶的非三进制,需要我们扩展先前的理论。特别是,我们确定了对煤子数编码的充足条件,我们展示了如何增强现有界面,即对煤子数型配料的精密计算,使上述扩展成为可能。两个扩展都有线性运行时间。