Paper Info
Title
The Parikh Property for Weighted Context-Free Grammars.
Abstract
Parikhu0027s Theorem states that every context-free grammar (CFG) is equivalent to some regular CFG when the ordering of symbols in the words is ignored. The same is not true for the so-called weighted CFGs, which additionally assign a weight to each grammar rule. If the result holds for a given weighted CFG $G$, we say that $G$ satisfies the Parikh property. We prove constructively that the Parikh property holds for every weighted nonexpansive CFG. We also give a decision procedure for the property when the weights are over the rationals.
Year
DOI
Venue
2018
10.4230/LIPIcs.FSTTCS.2018.32
FSTTCS
DocType
Volume
Citations 
Conference
abs/1810.01351
0
PageRank 
References 
Authors
0.34
9
2
Name
Order
Citations
PageRank
Pierre Ganty124220.29
Elena Gutiérrez200.68