Hardness of a separation of nondeterminism, randomization and determinism for polynomial time computations motivates the analysis of restricted models of computation. Following this line of research, we consider randomized length-reducing two-pushdown automata (IrTPDA), a natural extension of pushdown automata (PDA). We separate randomized IrTPDAs from deterministic and nondeterministic ones, and we compare different modes of randomization. Moreover, we prove that amplification is impossible for Las Vegas automata.
展开▼
