Skip to Main content Skip to Navigation
Conference papers

Random Generation of Deterministic Tree (Walking) Automata

Pierre-Cyrille Héam 1, 2 Cyril Nicaud 3 Sylvain Schmitz 1
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Uniform random generators deliver a simple empirical means to estimate the average complexity of an algorithm. We present a general rejection algorithm that generates sequential letter-to-letter transducers up to isomorphism. We tailor this general scheme to randomly generate deterministic tree walking automata and deterministic top-down tree automata. We apply our implementation of the generator to the estimation of the average complexity of a deterministic tree walking automata to nondeterministic top-down tree automata construction we also implemented.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Sylvain Schmitz <>
Submitted on : Thursday, July 30, 2009 - 11:34:37 AM
Last modification on : Monday, February 15, 2021 - 10:39:05 AM
Long-term archiving on: : Monday, October 15, 2012 - 3:41:44 PM


Files produced by the author(s)



Pierre-Cyrille Héam, Cyril Nicaud, Sylvain Schmitz. Random Generation of Deterministic Tree (Walking) Automata. 14th International Conference on Implementation and Application of Automata - CIAA 2009, Jul 2009, Sydney, Australia. pp.115--124, ⟨10.1007/978-3-642-02979-0_15⟩. ⟨inria-00408316⟩



Record views


Files downloads