Random Generation of Nondeterministic Finite-State Tree Automata

Thomas Hanneforth
(Universität Potsdam)
Andreas Maletti
(Universität Stuttgart)
Daniel Quernheim
(Universität Stuttgart)

Algorithms for (nondeterministic) finite-state tree automata (FTAs) are often tested on random FTAs, in which all internal transitions are equiprobable. The run-time results obtained in this manner are usually overly optimistic as most such generated random FTAs are trivial in the sense that the number of states of an equivalent minimal deterministic FTA is extremely small. It is demonstrated that nontrivial random FTAs are obtained only for a narrow band of transition probabilities. Moreover, an analytic analysis yields a formula to approximate the transition probability that yields the most complex random FTAs, which should be used in experiments.

In Sebastian Maneth: Proceedings Second International Workshop on Trends in Tree Automata and Tree Transducers (TTATT 2013), Hanoi, Vietnam, 19/10/2013, Electronic Proceedings in Theoretical Computer Science 134, pp. 11–16.
Andreas Maletti and Daniel Quernheim were financially supported by the German Research Foundation (DFG) grant MA/4959/1-1.
Published: 20th November 2013.

ArXived at: http://dx.doi.org/10.4204/EPTCS.134.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org