Incremental NFA Minimization

Finite state automata are fundamental objects in Theoretical Computer Science and find their application in Text Processing, Compilers Design, Artificial Intelligence and many other areas. The problem of minimizing such objects can be traced back to the '50s and since then it has been the arena for developing new algorithmic ideas. There are two main paradigms to tackle the problem: top down - which builds a descending chain of equivalences by subsequent refinements - and bottom up - which builds an ascending chain of equivalences by aggregation of classes. The former approach leads to a fast O(n log n) algorithm, whereas the latter is currently quadratic for any practical application. Nevertheless, the bottom up algorithm enjoys the property of being incremental, i.e. the minimization process can be stopped at any time obtaining a language-equivalent partially minimized automaton. In this work we correct a small mistake in the algorithm given by Almeida et al. in 2014 and we propose a simple, DFS-like and truly quadratic incremental algorithm for minimizing deterministic automata. Furthermore, we adapt the idea to the nondeterministic case obtaining an incremental algorithm which computes the maximum bisimulation relation in time O(n2r∣Σ∣), where n is the number of states, Σ is the alphabet and r is the degree of nondeterminism, improving by a factor of r the running time of the fastest known aggregation based algorithm for this problem.