Title: | Extending Parikh's Theorem to Weighted and Probabilistic Context-Free Grammars |
Author(s): | Bhattiprolu, Vijay; Gordon, Spencer; Viswanathan, Mahesh |
Subject(s): | weighted automata, probabilistic automata, Parikh's Theorem |
Abstract: | We prove an analog of Parikh's theorem for weighted context-free
grammars over commutative, idempotent semirings, and exhibit a
stochastic context-free grammar with behavior that cannot be realized
by any stochastic right-linear context-free grammar. Finally, we show
that every unary stochastic context-free grammar with
polynomially-bounded ambiguity has an equivalent stochastic
right-linear context-free grammar. |
Issue Date: | 2017-06-23 |
Genre: | Article |
Type: | Text |
Language: | English |
URI: | http://hdl.handle.net/2142/96262 |
Date Available in IDEALS: | 2017-06-23 |