Attribute grammars and automatic complexity analysis - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2000

Attribute grammars and automatic complexity analysis

Marni Mishna
  • Fonction : Auteur

Résumé

Decomposable combinatorial structures have been well studied and a systematic manner for determining generating function equations is well known. Attribute grammars have enhanced the study of context-free grammars by giving meaning to constructions. Delest and Fédou \citeDeFe92 showed that attribute grammars extend to combinatorial structures, with applications to random generation. In a similar way, we show attribute grammars can be defined for the family of decomposable structures and yield multivariate generating function equations. From there, averages and higher moments are easily accessible. This idea unifies previous approaches to the analysis of parameters of data-structures.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-4021.pdf (338.62 Ko) Télécharger le fichier

Dates et versions

inria-00072620 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00072620 , version 1

Citer

Marni Mishna. Attribute grammars and automatic complexity analysis. [Research Report] RR-4021, INRIA. 2000. ⟨inria-00072620⟩
30 Consultations
153 Téléchargements

Partager

Gmail Facebook X LinkedIn More