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

Yann Ponty 1, 2
2 AMIB - Algorithms and Models for Integrative Biology
CNRS - Centre National de la Recherche Scientifique : UMR8623, Polytechnique - X, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
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.
Type de document :
Rapport
[Research Report] 2012
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00693600
Contributeur : Yann Ponty <>
Soumis le : mercredi 2 mai 2012 - 18:42:09
Dernière modification le : jeudi 11 janvier 2018 - 06:23:08
Document(s) archivé(s) le : vendredi 3 août 2012 - 02:55:56

Fichiers

NoteWeightedGrammars.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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

Citation

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

Partager

Métriques

Consultations de la notice

285

Téléchargements de fichiers

161