Random Generation and Enumeration of Accessible Determinisitic Real-time Pushdown Automata

Pierre-Cyrille Héam 1, 2 Jean-Luc Joly 1, 2, *
* Auteur correspondant
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 Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : This papers presents a general framework for the uniform random generation of deterministic real-time accessible pushdown au-tomata. A polynomial time algorithm to randomly generate a pushdown automaton having a fixed stack operations total size is proposed. The influence of the accepting condition (empty stack, final state) on the reachability of the generated automata is investigated.
Type de document :
Communication dans un congrès
Frank Drewes. CIAA 2015, Aug 2015, Umea, Sweden. Springer, 9223, pp.12, 2015, Implementation and Application of Automata - 20th International Conference
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01087748
Contributeur : Pierre-Cyrille Heam <>
Soumis le : mardi 15 décembre 2015 - 15:25:10
Dernière modification le : jeudi 15 février 2018 - 08:48:14
Document(s) archivé(s) le : mercredi 16 mars 2016 - 14:10:24

Fichiers

PDA-HAL.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01087748, version 2
  • ARXIV : 1512.05881

Citation

Pierre-Cyrille Héam, Jean-Luc Joly. Random Generation and Enumeration of Accessible Determinisitic Real-time Pushdown Automata. Frank Drewes. CIAA 2015, Aug 2015, Umea, Sweden. Springer, 9223, pp.12, 2015, Implementation and Application of Automata - 20th International Conference. 〈hal-01087748v2〉

Partager

Métriques

Consultations de la notice

271

Téléchargements de fichiers

84