Random generation and enumeration of accessible deterministic real-time pushdown automata

DOI10.1007/978-3-319-22360-5_13MaRDI QIDQ2947417zbMATH OpenOpenAlexFDO

Authors Jean-Luc Joly, Pierre-Cyrille Héam

Publication date 23 September 2015

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.05881

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorial probability (60C05)

Abstract: This papers presents a general framework for the uniform random generation of deterministic real-time accessible pushdown automata. 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.

Recommendations

• Enumeration and random generation of possibly incomplete deterministic automata
• Random generation of deterministic acyclic automata using Markov chains
• Random generation of deterministic acyclic automata using the recursive method
• scientific article; zbMATH DE number 2087229
• Random Generation of Deterministic Tree (Walking) Automata

Cites work

• scientific article; zbMATH DE number 3645067 (Why is no real title available?)
• scientific article; zbMATH DE number 3913686 (Why is no real title available?)
• scientific article; zbMATH DE number 4039297 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1232241 (Why is no real title available?)
• A calculus for the random generation of labelled combinatorial structures
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Distribution of the number of accessible states in a random deterministic automaton
• Elements of automata theory. Translated from the French by Reuben Thomas
• Enumeration and random generation of accessible automata
• Enumeration and random generation of possibly incomplete deterministic automata
• Exact enumeration of acyclic deterministic automata
• Parametric random generation of deterministic tree automata
• REGAL: A Library to Randomly and Exhaustively Generate Automata
• Random deterministic automata
• Random generation of DFAs
• Random generation of deterministic acyclic automata using Markov chains

Cited in

(2)

• A random testing approach using pushdown automata
• Enumeration and random generation of accessible automata

This page was built for publication: Random generation and enumeration of accessible deterministic real-time pushdown automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947417)