A fast implementation of incremental minimization of tree automata
Younes Guellouma, Attia Nehar, Hadda Cherroun, Djelloul Ziadi · 2012
We address the problem of minimizing tree automata especially its incremental version. Unlike the classical minimization, incremental version [1] computes equivalences between states in the safe way, like that the algorithm may be halted at any moment, returning a partially minimized tree automata. However, this incremental version has worse time complexity compared with the classical one which runs in quadratic time of the tree automata size. The purpose of this paper is to improve the implementation of the incremental version. This improvement relies on classical properties of equivalence relations and some implementation tricks.