Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Language equivalence of probabilistic pushdown automata
Forejt V., Jančar P., Kiefer S., Worrell J. Information and Computation237 1-11,2014.Type:Article
Date Reviewed: Jan 26 2015

A probabilistic pushdown automaton (PDA) maps a state and a letter on top of the pushdown stack to a probability distribution over states and stack actions (pushes and pops). Thus, it lies between a deterministic and a nondeterministic PDA. Equivalence of accepted languages is decidable if we are given two deterministic PDAs and undecidable if we are given two nondeterministic PDAs. In a probabilistic PDA (PPDA), a word is accepted with a probability obtained by summing over all runs, say accepting by empty stack. Zero probability is interpreted as rejection. The language equivalence problem for PPDA asks whether two configurations (state and stack contents) accept each word over the input alphabet with the same probability.

The PDA to context-free grammar reduction was shown by Rosenkrantz to be polynomial time [1]. The authors show that this carries over to a reduction from ppda to “multigrammars” (the tricky part is keeping the conversion of a grammar to Greibach normal form in polynomial time), and hence to context-free grammars with finite multiplicity. Deciding whether two finite-multiplicity context-free grammars are equivalent up to multiplicity is a longstanding open problem [2]. The authors also give a polynomial space upper bound when the input alphabet is unary.

Reviewer:  K. Lodaya Review #: CR143109 (1504-0299)
1) Rosenkrantz, D. J. Matrix equations and normal forms for context-free grammars. J. ACM 14, 3(1967), 501–507.
2) Kuich, W. Results and trends in theoretical computer science (LNCS 812). Springer, 1994.
Bookmark and Share
 
Formal Languages (F.4.3 )
 
 
Probabilistic Computation (F.1.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Formal Languages": Date
The three subfamilies of rational &ohgr;-languages closed under &ohgr;-transduction
Timmerman E. Theoretical Computer Science 76(2-3): 243-250, 2001. Type: Article
Jul 1 1992
Introduction to formal languages
Révész G., Dover Publications, Inc., New York, NY, 1991. Type: Book (9780486666976)
Jan 1 1993
Fibonacci morphisms and Sturmian words
Séébold P. Theoretical Computer Science 88(2): 365-384, 1991. Type: Article
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy