2023/07/28 by Takahiro Sanada, Ryota Kojima, Sanada, Takahiro +7
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic, Reasoning, and Knowledge #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2307.15261
openalex publication_date 2023/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Algorithms for partition refinement are actively studied for a variety of systems, often with the optimisation called Hopcroft's trick. However, the low-level description of those algorithms in the literature often obscures the essence of Hopcroft's trick. Our contribution is twofold. Firstly, we present a novel formulation of Hopcroft's trick in terms of general trees with weights. This clean and explicit formulation -- we call it Hopcroft's inequality -- is crucially used in our second contribution, namely a general partition refinement algorithm that is functor-generic (i.e. it works for a variety of systems such as (non-)deterministic automata and Markov chains). Here we build on recent works on coalgebraic partition refinement but depart from them with the use of fibrations. In particular, our fibrational notion of R-partitioning exposes a concrete tree structure to which Hopcroft's inequality readily applies. It is notable that our fibrational framework accommodates such algorithmic analysis on the categorical level of abstraction.