Properties of probabilistic pushdown automata

Authors: Ioan I Macarie Mitsunori Ogihara

Publish Date: 1995/8/22

Volume: , Issue: , Pages: 343-352

PDF Link

Abstract

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 wellknown complexity classes are given for the classes of languages recognized by polynomial timebounded logarithmic spacebounded 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 DiffSAC1 is characterized as the difference between the number of stack symbols that is whether the stack alphabet contains one versus two distinct symbols

Keywords: