Over the years, bisimulations have emerged as a pervasive paradigm, finding applications in concurrency theory, model checking, automata theory, logic, programming languages, and category theory. This paper establishes a connection between bisimulations and data compression, particularly focusing on the relationship with Wheeler automata (Alanko et al., SODA 2020).
The standard notion of bisimulation is inappropriate, prompting the introduction of Wheeler bisimulations, which respect the convex structure of the considered Wheeler automata. We demonstrate that Wheeler bisimilarity induces a unique minimal Wheeler NFA, analogous to standard bisimulations.
Specifically, in the deterministic case, we recover the minimal Wheeler deterministic automaton of a given language. We also show that the minimal Wheeler NFA induced by Wheeler bisimulations can be constructed in linear time. This contrasts with standard bisimulations, where the corresponding minimal NFA can be built in $O(m \log n)$ time (with $m$ as the number of edges and $n$ as the number of states) by adapting the Paige-Tarjan partition refinement algorithm.
Compared to previous state-reduction techniques, our bisimulation-induced construction is the first to achieve (i) a canonical Wheeler NFA and (ii) a resulting Wheeler NFA that can be built in linear time.
Blogger's Review: The innovation of this paper lies in integrating bisimulations with Wheeler automata, providing a new perspective on the minimization process of automata. The ability to construct a minimal Wheeler NFA in linear time signifies a significant advancement in theoretical computer science, meriting further research and application.