Helmut Seidl. On the Finite Degree of Ambiguity of Finite Tree Automata. In János Csirik, János Demetrovics and Ferenc Gécseg, editors, Fundamentals of Computation Theory, volume 380 of Lecture Notes in Computer Science, pages 395-404, Szeged, Hungary, August 1989. Springer.

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 The original publication is available at www.springerlink.com