Random Generation and Enumeration of Accessible Determinisitic Real-time Pushdown Automata
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.
Domains
Computation and Language [cs.CL]
Origin : Files produced by the author(s)
Loading...