Attribute Grammars and Automatic Algorithm Analysis

Marni Mishna

To appear at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), May 20-26, 2001


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\'edou \cite{DeFe92} 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. Les structures decomposables sont bien etudi\'ees, et une m\'ethode systematique permettant d'obtenir des \'equations de fonctions g\'en\'eratrices est bien connue. Les grammaires attribu\'ees permettent de donner une signification aux constructions des grammaires context-free. Delest et F\'edou ont montr\'e que les grammaires attribu\'ees s'\'etendent \`a certaines structures combinatoires, avec des applications \`a la g\'en\'eration al\'eatoire. De mani\`ere semblable, nous montrons que des grammaires attribu\'ees peuvent \^etre definies pour la famille des structures decomposables, ce qui donne lieu \`a des equations de fonctions g\'en\'eratrices multivari\'ees. De l\`a, moyennes et autres moments sont ais\'ement accessibles. Cett id\'ee unifie les approches pr\'ec\'edentes \`a l'analyse de param\`etres des structures de donn\'ees

Server START Conference Manager
Update Time 23 Feb 2001 at 08:48:02
Start Conference Manager
Conference Systems