文章基本信息

标题：The Parikh Property for Weighted Context-Free Grammars
本地全文：下载
作者：Pierre Ganty ; Elena Guti{\'e}rrez
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：122
页码：1-20
DOI：10.4230/LIPIcs.FSTTCS.2018.32
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Parikh's 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.
关键词：Weighted Context-Free Grammars; Algebraic Language Theory; Parikh Image