Attribute grammars and automatic complexity analysis

Marni Mishna 1
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : 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.
Type de document :
Rapport
[Research Report] RR-4021, INRIA. 2000
Liste complète des métadonnées

https://hal.inria.fr/inria-00072620
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 10:24:49
Dernière modification le : samedi 17 septembre 2016 - 01:29:46
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:15:39

Fichiers

Identifiants

  • HAL Id : inria-00072620, version 1

Collections

Citation

Marni Mishna. Attribute grammars and automatic complexity analysis. [Research Report] RR-4021, INRIA. 2000. 〈inria-00072620〉

Partager

Métriques

Consultations de la notice

63

Téléchargements de fichiers

122