Rule-weighted and terminal-weighted context-free grammars have identical expressivity - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

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

Résumé

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
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

Yann Ponty. Rule-weighted and terminal-weighted context-free grammars have identical expressivity. [Research Report] 2012. ⟨hal-00693600⟩
239 Consultations
184 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More