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

Yann Ponty 1, 2
2 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
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.
Document type :
Reports
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00693600
Contributor : Yann Ponty <>
Submitted on : Wednesday, May 2, 2012 - 6:42:09 PM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on : Friday, August 3, 2012 - 2:55:56 AM

Files

NoteWeightedGrammars.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00693600, version 1
  • ARXIV : 1205.0627

Collections

Citation

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

Share

Metrics

Record views

453

Files downloads

249