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

DOI10.1007/978-3-319-22360-5_13zbMATH Open1465.68147arXiv1512.05881OpenAlexW1467747090MaRDI QIDQ2947417FDOQ2947417

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)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• REGAL: A Library to Randomly and Exhaustively Generate Automata
• Elements of automata theory. Translated from the French by Reuben Thomas
• Title not available (Why is that?)
• Random generation of DFAs
• Enumeration and random generation of accessible automata
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• A calculus for the random generation of labelled combinatorial structures
• Enumeration and random generation of possibly incomplete deterministic automata
• Parametric random generation of deterministic tree automata
• Exact enumeration of acyclic deterministic automata
• Title not available (Why is that?)
• Random generation of deterministic acyclic automata using Markov chains
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distribution of the number of accessible states in a random deterministic automaton
• Random deterministic automata
• Title not available (Why is that?)

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)