Random Generation and Enumeration of Accessible Determinisitic Real-time Pushdown Automata
Pierre‐Cyrille Héam, Joly, Jean-Luc · arXiv (Cornell University) · 2015
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.