Files in this item

FilesDescriptionFormat

application/pdf

application/pdfpaper.pdf (299kB)
(no description provided)PDF

Description

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


This item appears in the following Collection(s)

Item Statistics