Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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

https://hal.inria.fr/inria-00408316
Contributor : Sylvain Schmitz Connect in order to contact the contributor
Submitted on : Thursday, July 30, 2009 - 11:34:37 AM
Last modification on : Thursday, January 20, 2022 - 5:29:57 PM
Long-term archiving on: : Monday, October 15, 2012 - 3:41:44 PM

File

RandomTA.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

302

Files downloads

117