Random Generation of Positive TAGEDs wrt. the Emptiness Problem

Pierre-Cyrille Heam 1 Vincent Hugot 1 Olga Kouchnarenko 1
1 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 Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Tree automata are a widely used formalism in Computer Science. Since their creation in the fifties, numerous more expressive extensions have been proposed. Unfortunately, the decision problems associated with these extensions are quite often undecidable or in prohibitive classes of algorithmic complexity (NP-complete or worse), and little work has gone into finding efficient heuristics for them. Beyond the inherent difficulty of those problems, a common hitch in this line of research is the experimental evaluation of new algorithms. As those extensions of tree automata have remained in chiefly theoretical spheres, there are no established testbeds from the "real world" against which to quantify the efficiency (or lack thereof) of new algorithms. Failing that, there is a need to generate suitable testbeds at random. Regrettably, there is little material in the literature regarding random generation of tree automata, and none at all regarding extensions such as Tree Automata with Global Equality and Disequality Constraints (TAGEDs). It should also be noted that what little material there is does not concern itself with the interest of the generated automata wrt. specific decision problems. In this report we present a scheme for random generation of positive TAGEDs, with a focus on making them interesting wrt. the Emptiness problem.
Type de document :
Rapport
[Research Report] RR-7441, INRIA. 2010, pp.43
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00531350
Contributeur : Olga Kouchnarenko <>
Soumis le : mardi 2 novembre 2010 - 14:50:52
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10
Document(s) archivé(s) le : vendredi 2 décembre 2016 - 00:57:44

Fichier

RR-7441.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00531350, version 1

Citation

Pierre-Cyrille Heam, Vincent Hugot, Olga Kouchnarenko. Random Generation of Positive TAGEDs wrt. the Emptiness Problem. [Research Report] RR-7441, INRIA. 2010, pp.43. 〈inria-00531350〉

Partager

Métriques

Consultations de la notice

387

Téléchargements de fichiers

125