Efficient Implementation for Deterministic Finite Tree Automata Minimization

摘要

We address the problem of deterministic finite tree automata (DFTA) minimization. We describe a new alternative to implement both standard and incremental tree automata minimization using a well-defined graph representing the automaton to be minimized. We show that the asymptotic complexity of the standard implementation is linearithmic and the incremental one is O(n~3 log(n)) where n is the DFTA size.