Explicit Hopcroft's Trick in Categorical Partition Refinement
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917655230808064 |
|---|---|
| author | Sanada, Takahiro Kojima, Ryota Komorida, Yuichi Muroya, Koko Hasuo, Ichiro |
| author_facet | Sanada, Takahiro Kojima, Ryota Komorida, Yuichi Muroya, Koko Hasuo, Ichiro |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_15261 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Explicit Hopcroft's Trick in Categorical Partition Refinement Sanada, Takahiro Kojima, Ryota Komorida, Yuichi Muroya, Koko Hasuo, Ichiro Formal Languages and Automata Theory 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. |
| title | Explicit Hopcroft's Trick in Categorical Partition Refinement |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2307.15261 |