The Equivalence Between Weighted top-down Tree Automata

This paper investigates the equivalence problem of weighted top-down tree automata over totally ordered lattices (or WTAs, for short). First, we define initialized WTA and some concepts corresponding to initialized WTA are given. Also, we prove the decidability of the equivalence problem for initialized WTAs. Next, we present an algorithmic procedure for deciding the equivalence between two initialized WTAs. Moreover, we analyze the complexity of the given algorithm. Finally, we give an example for the equivalence problem.

Keywords:

Weighted top-down tree automata , Equivalence problem , Totally ordered lattice