2026-07-23T21:29:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9931 2024-03-06T10:45:08Z ddc:004 open_access

The Parikh Property for Weighted Context-Free Grammars Ganty, Pierre Gutiérrez, Elena Weighted Context-Free Grammars Algebraic Language Theory Parikh Image 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pierre Ganty and Elena Gutiérrez 2018 Is Part Of LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2018.32 urn:nbn:de:0030-drops-99315 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.32 eng https://creativecommons.org/licenses/by/3.0/legalcode