ALCOMFT-TR-01-168

Marni Mishna
Attribute Grammars and Automatic Complexity Analysis
INRIA. Work package 4. June 2001.

Abstract: Attribute grammars provide a concise way to describe traits of a wide family of structures. Structures defined by context free grammars have been well studied by Delest, Fédou and more recently by Duchon. One of hte principle benefits of this approach is the easy access to multi-vairate generating function equations from which average and higher moments are easily accessible. this work extends these notions to a wider class of structures and considers the application to algorithm analysis.

Postscript file: ALCOMFT-TR-01-168.ps.gz (73 kb).