Rule-weighted and terminal-weighted context-free grammars have identical expressivity - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2012

Rule-weighted and terminal-weighted context-free grammars have identical expressivity

(1, 2)
1
2

Abstract

Two formalisms, both based on context-free grammars, have recently been proposed as a basis for a non-uniform random generation of combinatorial objects. The former, introduced by Denise et al, associates weights with letters, while the latter, recently explored by Weinberg et al in the context of random generation, associates weights to transitions. In this short note, we use a simple modification of the Greibach Normal Form transformation algorithm, due to Blum and Koch, to show the equivalent expressivities, in term of their induced distributions, of these two formalisms.
Fichier principal
Vignette du fichier
NoteWeightedGrammars.pdf (126.7 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00693600 , version 1 (02-05-2012)

Identifiers

Cite

Yann Ponty. Rule-weighted and terminal-weighted context-free grammars have identical expressivity. [Research Report] 2012. ⟨hal-00693600⟩
231 View
171 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More