Hyper-minimization for deterministic weighted tree automata

A Maletti, D Quernheim - arXiv preprint arXiv:1405.5610, 2014 - arxiv.org
A Maletti, D Quernheim
arXiv preprint arXiv:1405.5610, 2014arxiv.org
Hyper-minimization is a state reduction technique that allows a finite change in the
semantics. The theory for hyper-minimization of deterministic weighted tree automata is
provided. The presence of weights slightly complicates the situation in comparison to the
unweighted case. In addition, the first hyper-minimization algorithm for deterministic
weighted tree automata, weighted over commutative semifields, is provided together with
some implementation remarks that enable an efficient implementation. In fact, the same run …
Hyper-minimization is a state reduction technique that allows a finite change in the semantics. The theory for hyper-minimization of deterministic weighted tree automata is provided. The presence of weights slightly complicates the situation in comparison to the unweighted case. In addition, the first hyper-minimization algorithm for deterministic weighted tree automata, weighted over commutative semifields, is provided together with some implementation remarks that enable an efficient implementation. In fact, the same run-time O(m log n) as in the unweighted case is obtained, where m is the size of the deterministic weighted tree automaton and n is its number of states.
arxiv.org