Hanneforth, Thomas and Maletti, Andreas and Quernheim, Daniel - Pushing for weighted tree automata

lmcs:4210 - Logical Methods in Computer Science, January 16, 2018, Volume 14, Issue 1
Pushing for weighted tree automata

Authors: Hanneforth, Thomas and Maletti, Andreas and Quernheim, Daniel

A weight normalization procedure, commonly called pushing, is introduced for weighted tree automata (wta) over commutative semifields. The normalization preserves the recognized weighted tree language even for nondeterministic wta, but it is most useful for bottom-up deterministic wta, where it can be used for minimization and equivalence testing. In both applications a careful selection of the weights to be redistributed followed by normalization allows a reduction of the general problem to the corresponding problem for bottom-up deterministic unweighted tree automata. This approach was already successfully used by Mohri and Eisner for the minimization of deterministic weighted string automata. Moreover, the new equivalence test for two wta $M$ and $M'$ runs in time $\mathcal O((\lvert M \rvert + \lvert M'\rvert) \cdot \log {(\lvert Q\rvert + \lvert Q'\rvert)})$, where $Q$ and $Q'$ are the states of $M$ and $M'$, respectively, which improves the previously best run-time $\mathcal O(\lvert M \rvert \cdot \lvert M'\rvert)$.


Source : oai:arXiv.org:1702.00304
DOI : 10.23638/LMCS-14(1:5)2018
Volume: Volume 14, Issue 1
Published on: January 16, 2018
Submitted on: February 2, 2017
Keywords: Computer Science - Formal Languages and Automata Theory,68Q45, 68Q25,F.4.2,F.4.3


Share

Consultation statistics

This page has been seen 139 times.
This article's PDF has been downloaded 43 times.