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

Pierre-Cyrille Héam 1, 2 Jean-Luc Joly 1, 2, *
* Corresponding author
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 : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01087748
Contributor : Pierre-Cyrille Heam <>
Submitted on : Tuesday, December 15, 2015 - 3:25:10 PM
Last modification on : Tuesday, December 18, 2018 - 4:38:25 PM
Long-term archiving on : Wednesday, March 16, 2016 - 2:10:24 PM

Files

PDA-HAL.pdf
Files produced by the author(s)

Identifiers

  • 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. CIAA 2015, Aug 2015, Umea, Sweden. pp.12. ⟨hal-01087748v2⟩

Share

Metrics

Record views

546

Files downloads

119