Random Generation of Deterministic Tree (Walking) Automata

Pierre-Cyrille Héam 1, 2 Cyril Nicaud 3 Sylvain Schmitz 1
1 LSV - Laboratoire Spécification et Vérification [Cachan]
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, INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 LIGM - Laboratoire d'Informatique Gaspard-Monge
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.
Keywords : random generation uniform distribution tree-walking automaton top-down automaton sequential transducer average complexity
Type de document :
Communication dans un congrès
Sebastian Maneth. 14th International Conference on Implementation and Application of Automata - CIAA 2009, Jul 2009, Sydney, Australia. Springer-Verlag, 5642, pp.115--124, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-02979-0_15〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00408316
Contributeur : Sylvain Schmitz <>
Soumis le : jeudi 30 juillet 2009 - 11:34:37
Dernière modification le : mercredi 11 avril 2018 - 12:12:02
Document(s) archivé(s) le : lundi 15 octobre 2012 - 15:41:44

Fichier

RandomTA.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | UNIV-FCOMTE | UNIV-MLV | LIGM | LIGM_ALGO | ENPC-LIGM | PARISTECH | ENPC | UPEC-UPEM | LIGM_MOA | UNIV-BM | FEMTO-ST | UNIV-BM-THESE | ENS-CACHAN | LORIA | UNIV-LORRAINE | TDS-MACS

Citation

Pierre-Cyrille Héam, Cyril Nicaud, Sylvain Schmitz. Random Generation of Deterministic Tree (Walking) Automata. Sebastian Maneth. 14th International Conference on Implementation and Application of Automata - CIAA 2009, Jul 2009, Sydney, Australia. Springer-Verlag, 5642, pp.115--124, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-02979-0_15〉. 〈inria-00408316〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

608

Téléchargements de fichiers

142

Contact


archive-ouverte@inria.fr