A Coalgebraic Paige-Tarjan Algorithm https://arxiv.org/abs/1705.08362 ここしばらく通勤中にずっと読んでた論文。 Paige-Tarjanの partition refinement アルゴリズムを、余代数で表現できる遷移系に一般化。

面白かったのだけど、同値関係 ≒ kernel や分割 ≒ regular epi を行き来する議論に不慣れで、ついていくのが中々大変で、だいぶ読むのに時間がかかってしまった。

あと、すごく一般化したアルゴリズムから初めて、高速化の工夫を入れて現実的なアルゴリズムにしてるのだけど、結局すべての工夫が入れられるのは実質的にラベル付き状態遷移系に帰着できる場合だけなので、だとしたら、ここまで一般的な話にしなくてもという気がしないでもない（いや、面白いんだけど）。