TY - GEN

T1 - Properties of probabilistic pushdown automata

T2 - 10th Conference on Fundamentals of Computation Theory, FCT 1995

AU - Macarie, Ioan I.

AU - Ogihara, Mitsunori

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.

PY - 1995

Y1 - 1995

N2 - Properties of probabilistic as well as “probabilistic plus nondeterministic” pushdown automata and auxiliary pushdown automata are studied. These models are analogous to their counterparts with nondeterministic and alternating states. Complete characterizations in terms of well-known complexity classes are given for the classes of languages recognized by polynomial time-bounded, logarithmic space-bounded auxiliary pushdown automata with probabilistic states and with “probabilistic plus nondeterministic” states. Also, complexity lower bounds are given for the classes of languages recognized by these automata with unlimited running time. It follows that, by fixing an appropriate mode of computation, the difference between classes of languages such as P and PSPACE, NL and SAC1, PL and Diff>(#SAC1) is characterized as the difference between the number of stack symbols; that is, whether the stack alphabet contains one versus two distinct symbols.

AB - Properties of probabilistic as well as “probabilistic plus nondeterministic” pushdown automata and auxiliary pushdown automata are studied. These models are analogous to their counterparts with nondeterministic and alternating states. Complete characterizations in terms of well-known complexity classes are given for the classes of languages recognized by polynomial time-bounded, logarithmic space-bounded auxiliary pushdown automata with probabilistic states and with “probabilistic plus nondeterministic” states. Also, complexity lower bounds are given for the classes of languages recognized by these automata with unlimited running time. It follows that, by fixing an appropriate mode of computation, the difference between classes of languages such as P and PSPACE, NL and SAC1, PL and Diff>(#SAC1) is characterized as the difference between the number of stack symbols; that is, whether the stack alphabet contains one versus two distinct symbols.

UR - http://www.scopus.com/inward/record.url?scp=84947912337&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84947912337&partnerID=8YFLogxK

U2 - 10.1007/3-540-60249-6_66

DO - 10.1007/3-540-60249-6_66

M3 - Conference contribution

AN - SCOPUS:84947912337

SN - 3540602496

SN - 9783540602491

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 343

EP - 352

BT - Fundamentals of Computation Theory - 10th International Conference, FCT 1995, Proceedings

A2 - Reichel, Horst

PB - Springer Verlag

Y2 - 22 August 1995 through 25 August 1995

ER -