Extending Parikh’s theorem to weighted and probabilistic context-free grammars

Vijay Bhattiprolu; Spencer Gordon; Mahesh Viswanathan

doi:10.1007/978-3-319-66335-7_1

Extending Parikh’s theorem to weighted and probabilistic context-free grammars

Vijay Bhattiprolu, Spencer Gordon, Mahesh Viswanathan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Quantitative Evaluation of Systems - 14th International Conference, QEST 2017, Proceedings
Editors	Nathalie Bertrand, Luca Bortolussi
Publisher	Springer
Pages	3-19
Number of pages	17
ISBN (Print)	9783319663340
DOIs	https://doi.org/10.1007/978-3-319-66335-7_1
State	Published - 2017
Event	14th International Conference on Quantitative Evaluation of Systems, QEST 2017 - Berlin, Germany Duration: Sep 5 2017 → Sep 7 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10503 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	14th International Conference on Quantitative Evaluation of Systems, QEST 2017
Country/Territory	Germany
City	Berlin
Period	9/5/17 → 9/7/17

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

10.1007/978-3-319-66335-7_1

Library availability

Discover UIUC Full Text

Cite this

Bhattiprolu, V., Gordon, S., & Viswanathan, M. (2017). Extending Parikh’s theorem to weighted and probabilistic context-free grammars. In N. Bertrand, & L. Bortolussi (Eds.), Quantitative Evaluation of Systems - 14th International Conference, QEST 2017, Proceedings (pp. 3-19). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10503 LNCS). Springer. https://doi.org/10.1007/978-3-319-66335-7_1

Extending Parikh’s theorem to weighted and probabilistic context-free grammars. / Bhattiprolu, Vijay; Gordon, Spencer; Viswanathan, Mahesh.

Quantitative Evaluation of Systems - 14th International Conference, QEST 2017, Proceedings. ed. / Nathalie Bertrand; Luca Bortolussi. Springer, 2017. p. 3-19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10503 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bhattiprolu, V, Gordon, S & Viswanathan, M 2017, Extending Parikh’s theorem to weighted and probabilistic context-free grammars. in N Bertrand & L Bortolussi (eds), Quantitative Evaluation of Systems - 14th International Conference, QEST 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10503 LNCS, Springer, pp. 3-19, 14th International Conference on Quantitative Evaluation of Systems, QEST 2017 , Berlin, Germany, 9/5/17. https://doi.org/10.1007/978-3-319-66335-7_1

Bhattiprolu V, Gordon S, Viswanathan M. Extending Parikh’s theorem to weighted and probabilistic context-free grammars. In Bertrand N, Bortolussi L, editors, Quantitative Evaluation of Systems - 14th International Conference, QEST 2017, Proceedings. Springer. 2017. p. 3-19. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-66335-7_1

Bhattiprolu, Vijay ; Gordon, Spencer ; Viswanathan, Mahesh. / Extending Parikh’s theorem to weighted and probabilistic context-free grammars. Quantitative Evaluation of Systems - 14th International Conference, QEST 2017, Proceedings. editor / Nathalie Bertrand ; Luca Bortolussi. Springer, 2017. pp. 3-19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f3857e1a40b94ed2b5ed8e9db83bb284,

title = "Extending Parikh{\textquoteright}s theorem to weighted and probabilistic context-free grammars",

abstract = "We prove an analog of Parikh{\textquoteright}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.",

author = "Vijay Bhattiprolu and Spencer Gordon and Mahesh Viswanathan",

note = "Publisher Copyright: {\textcopyright} 2017, Springer International Publishing AG.; 14th International Conference on Quantitative Evaluation of Systems, QEST 2017 ; Conference date: 05-09-2017 Through 07-09-2017",

year = "2017",

doi = "10.1007/978-3-319-66335-7_1",

language = "English (US)",

isbn = "9783319663340",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "3--19",

editor = "Nathalie Bertrand and Luca Bortolussi",

booktitle = "Quantitative Evaluation of Systems - 14th International Conference, QEST 2017, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Extending Parikh’s theorem to weighted and probabilistic context-free grammars

AU - Bhattiprolu, Vijay

AU - Gordon, Spencer

AU - Viswanathan, Mahesh

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

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

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

U2 - 10.1007/978-3-319-66335-7_1

DO - 10.1007/978-3-319-66335-7_1

M3 - Conference contribution

AN - SCOPUS:85028658413

SN - 9783319663340

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

SP - 3

EP - 19

BT - Quantitative Evaluation of Systems - 14th International Conference, QEST 2017, Proceedings

A2 - Bertrand, Nathalie

A2 - Bortolussi, Luca

PB - Springer

T2 - 14th International Conference on Quantitative Evaluation of Systems, QEST 2017

Y2 - 5 September 2017 through 7 September 2017

ER -

Extending Parikh’s theorem to weighted and probabilistic context-free grammars

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this