Helmut Seidl. On the Finite Degree of Ambiguity of Finite Tree Automata. Acta Inf., 26(6):527-542, 1989.

The degree of ambiguity of a finite tree automaton $\mathnormal {A}$ , da( $\mathnormal {A}$ ), is the maximal number of different accepting computations of $\mathnormal {A}$ for any possible input tree. We show: it can be decided in polynomial time whether or not da( $\mathnormal {A}$ ) ${<}\infty$ . We give two criteria characterizing an infinite degree of ambiguity and derive the following fundamental properties of an finite tree automaton $\mathnormal {A}$ with $\mathnormal {n}$ states and rank $\mathnormal {L}{>}1$ having a finite degree of ambiguity: for every input tree $\mathnormal {t}$ there is a input tree $\mathnormal {t}_1$ of depth less than $2^{2n} \cdot n$ ! having the same number of accepting computations; the degree of ambiguity of $\mathnormal {A}$ is bounded by $2^{2^2\cdot log(L+1)\cdot n}$ .

Download: PDF Reference: Bibtex