From tree automata to string automata minimization (Q722214)

The authors associate with any given deterministic finite bottom-up tree automaton (DFTA) a deterministic finite string automaton (DFA) that can be used for minimizing the tree automaton. By this reduction the existing efficient minimization algorithms designed for string automata become applicable to tree automata. Thus, using a standard minimization method for DFAs, a DFTA can be minimized in time \(\mathcal{O}(rm + m \log n)\), where \(r\) is the maximal rank in the ranked alphabet, \(m\) is the size of the DFTA and \(n\) is the number of its states. The reduction yields also efficient methods for minimizing acyclic DFTAs, as well as for incremental minimization and incremental construction of DFTAs.