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

International audienceThis 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