Probabilistic Length-Reducing Two-Pushdown Automata |
| |
Authors: | Tomasz Jurdziński |
| |
Affiliation: | (1) Institute of Computer Science, University of Wrocław, Joliot-Curie 15, 50-383 Wrocław, Poland |
| |
Abstract: | Hardness of a separation of nondeterminism, randomization and determinism for polynomial time computations has motivated the
analysis of this issue for restricted models of computation. Following this line of research, we consider randomized length-reducing
two-pushdown automata (
), a natural extension of pushdown automata (
). Our main results are as follows. We show that deterministic
s are weaker than Las Vegas
s which in turn are weaker than Monte Carlo
s. Moreover, bounded two-sided error
s are stronger than Monte Carlo
s and they are able to recognize some languages which cannot be recognized nondeterministically. Finally, we prove that amplification
is impossible for Las Vegas and Monte Carlo automata.
Partially supported by MNiSW grant number N206 024 31/3826, 2006-2008. An extended abstract of this paper appeared in the
MFCS06 Proceedings (Lecture Notes in Computer Science, vol. 4162, pp. 561–572, 2006). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|