The Parikh Property for Weighted Context-Free Grammars
| Autor: | Ganty, Pierre, Gutiérrez, Elena |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.4230/LIPIcs.FSTTCS.2018 |
| Popis: | 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. Comment: 29 pages, 2 figures, long version of FSTTCS'18 paper |
| Databáze: | arXiv |
| Externí odkaz: |
|