An attribute grammar defines the values of a structure in a combstruct grammar. This is done in a recursive manner, where the value of a structure depends on the values of its substructures, and the atoms take on constant values.  For example, the internal pathlength (ipl) of a rooted tree is the sum of all the distances from the nodes to the root. This can be described very easily from the recursive description of trees.

First determine the ipl for a subtree. Notice that the distance from a node to the root is one more than to the root of the subtree. When you add up all of these "one mores" you have the size of the subtree.

The interpretation of the attribute syntax for ipl is the following:

Given a structure of type T, there are two cases.

It is Z, in which case ipl(T)=0, or it is of the form Prod(Z, T, T), in which case the value is the sum of the pathlengths of the two children trees, plus the sizes of the two subtrees. The values are additive and so the notation implies that the value of the product is the sum over all of the components. The number of atoms, or size, is a predefined attribute.

The specification of an attribute is highly dependent upon the specification of the structure. Thus, the syntax for specifying the attributes mirrors the structures themselves.  In the case of iterative operators such as Set, Cycle, and Sequence, the function is a sum over all the members. That is, given the definition for nonplane trees of

you can determine, in a fashion similar to the previous example, the pathlength for this type of tree.

The convention adopted is that the value of an attribute of a set is defined as the sum over the value defined for its elements. Thus, given the attribute definition F(A)=Set(G(B)), interpret the value of the set $\left\{b_1\,b_2\,b_3\right\}$ in A, for example, as $G\left(b_1\right)\+G\left(b_2\right)\+G\left(b_3\right)$. The same convention is used for Sequences, Cycles, and PowerSets. The pathlength is calculated as a sum of a function of the subtrees in Set(T). Thus, the attribute grammar for ipl of nonplane trees is defined.

The values must be a linear function of attributes of the substructures. For example, the following attribute is not acceptable in this system.

The coefficients and constants must each be of type atomic.

Attributes of a structure type can be defined in terms of other attributes of the structure type, provided there is no circularity. For example, the ipl could alternately be defined as the following.

In this last example, the T refers to the T from the left-hand side of the production rule.

Generating functions are the main analytical tool in this setting. For a detailed introduction into the use of the generating function as an enumerative tool in the combstruct setting, see Generating functions.

Multivariate generating functions can count the number of structures of a specified size with particular values for a specified attribute. Each attribute is assigned a variable and the multivariate generating function encodes the enumerative  information. For example, in an unlabeled system with two attributes $f_1$ and $f_2$ and structure type  $A$,  the multivariate generating function is

$A\left(z\,q_1\,q_2\right)\=\sum _A{z}^{\left|a\right|}{q}_1^{f_1\left(a\right)}{q}_2^{f_2\left(a\right)}$,

where the sum is over all structures a of type A, and |a| indicates the size or number of atoms in a.

Thus, in the tree example the generating function,  $T\left(z\,u\right)$ with $u$ marking pathlength, has  $\left[z^n{u}^m\right]T\left(z\,u\right)$  trees with $n$ atoms and pathlength $m$, where the notation $\left[z^n{u}^m\right]T\left(z\,u\right)$ means the coefficient of $z^n{u}^m$ in the series development of $T\left(z\,u\right)$. To determine the generating function equations use the command combstruct[agfeqns].

The command to determine the truncated series expansion is combstruct[agfseries].

You can deduce from this that the number of trees T on 7 nodes with ipl(T) =12 is 4. Once the generating functions are found, the coefficients can be extracted and manipulated. You can solve for the generating function for trees, without any attributes.

Averages and higher moments can be solved by differentiation. For example, determine the generating function of ${\mathrm{D}}_u\left(T\right)\left(z\,1\right)$, the partial derivative with respect to u of T(z,u), evaluated at 1 to do an average case analysis.

To calculate the average value of an attribute over all structures of a given size, first determine the number of structures (num(n)), and the sum of averages of values for all data structures of a given size, (avg_sum(n)).  The quotient $\mathrm{avg}\left(n\right)\=\frac{\mathrm{avg\_sum}\left(n\right)}{\mathrm{num}\left(n\right)}$,  is the average value for a structure of size n. The calculations are done with generating functions in the following way. Determine relations for  $A\left(z\,u\right)\=\sum _{a\=A}{u}^{\mathrm{cost}\left(a\right)}{z}^{\mathrm{size}\left(a\right)}$, and solve for  ${\mathrm{D}}_{u}A\left(z\,1\right)\=\sum _{a\=A}\mathrm{cost}\left(a\right)z^{\mathrm{size}\left(a\right)}$, which is equal to $\sum _n\mathrm{avg\_sum}\left(n\right)z^n$.   Variance and higher moments are also accessible with this approach.

To determine the variance, use the identity

$\mathrm{Var}\left[z\right]\=E\left[z^2\right]-{\left(E\left[z\right]\right)}^2$, and calculate E[$z^2$] from the second factorial moment, ${\mathrm{D}}_{u^2}A\left(z\,1\right)\=\sum _{a\=A}\mathrm{cost}\left(a\right)\left(\mathrm{cost}\left(a\right)-1\right)z^{\mathrm{size}\left(a\right)}$  added to ${\mathrm{D}}_{u}A\left(z\,1\right)$.

Determine these values by series manipulation.

Or use the function combstruct[agfmomentsolve] to do this calculation on the level of the generating function equations and solve the result.

To solve for higher moments, take higher derivatives (which correspond to higher values of k in agfmomentsolve(eqns, k)).

The following examples use attribute grammars to resolve combinatorial problems. They are based on problems in "The Lambda-Upsilon-Omega: The 1989 Cookbook" (see references below). You can find more information on these problems there.

This is an abridged version of a more detailed worksheet. If these types of problems interest you, consider using the algolib package, available at  http://algo.inria.fr/libraries. The algolib package contains tools for asymptotic analysis of generating function coefficients.

Regular Languages and Finite Automata

If you restrict your grammar constructors to those structures generated by Prods and Unions, you obtain the class of regular languages. As regular languages are equivalent to those accepted by finite automaton, you can view attribute grammars as output for each transition within the finite automaton. The next examples are based on this idea. The algorithm is like running a finite automaton on an input string, where the output at each transition is "cost". Each example determines the  average cost of an input of size $n$.     Since the grammars use only Unions and Prods in a simple way, their generating functions are simple enough, that is, rational. You can solve for the coefficients directly. To do this, use the genfunc package. The following function extracts the coefficient of $z^n$ from F(z). >  ncoeff:= proc(F,z,n) rsolve({genfunc[rgf_sequence]('boundary', F, z, a, n),genfunc[rgf_sequence]('recur', F, z, a, n)},a(n)); end: Naive Treatment of Addition Chains The problem is to efficiently compute the "exponential" $x^c$ in a group structure G. Instead of multiplying x to itself c times, square x a certain number of times and multiply certain squares together. The number of multiplications and squarings is directly linked to the binary expression of c, hence this method is called the binary method. For example, $x^8\={\left({\left(x^2\right)}^2\right)}^2$ can be calculated with 3 squarings and 8=(1000), whereas 10=(1010) implies  $x^{10}\={\left({\left(x^2\right)}^2\right)}^2{\left(x^2\right)}^2$, that is, three squarings and one multiplication. This is far more efficient than 10 multiplications.   To determine the total number of operations in the process, parse the binary representation of c. Encountering a 0 is equivalent to a squaring, encountering a one is equivalent to a squaring and multiplication. Omit the leading one since the first term has nothing with which to multiply itself. Hence, the basic structure considered is a binary string.   Define the complexity of this operation to be the number of multiplications including squarings. Determine the average complexity in terms of n of this algorithm for c such that ${\log }_2\left(c\right)\=n$.  The basic data structure, the binary string, corresponding to c. The cost of the chain is the cost over all the bits.  Let   >  GG[chn]:= {Chain = Sequence(Bit), Bit= Union(zero, one), zero = Atom,one = Atom}: AG[chn]:= {cost(Chain)= Sequence(cost(Bit)), cost(zero)=sq+mul, cost(one)=sq+mul}: Next, determine the multivariate generating function equations corresponding to this system. >  EQ[chn]:=agfeqns(GG[chn], AG[chn], unlabeled, z, [[u, cost]]); ${\mathrm{EQ}}_{\mathrm{chn}}:=\left[\mathrm{Bit}\left(z\,u\right)\=2z{u}^{\mathrm{sq}\+\mathrm{mul}}\,\mathrm{Chain}\left(z\,u\right)\=\frac{1}{1-\mathrm{Bit}\left(z\,u\right)}\,\mathrm{one}\left(z\,u\right)\=z{u}^{\mathrm{sq}\+\mathrm{mul}}\,\mathrm{zero}\left(z\,u\right)\=z{u}^{\mathrm{sq}\+\mathrm{mul}}\right]$ (3.1.1.1) If you set u=1 and solve, the generating function for Chains is obtained. If you differentiate with respect to u and set u=1, the grand average generating function is obtained. >  gf[chn]:=subs(agfmomentsolve(EQ[chn],0), Chain(z)); agf[chn]:=subs(agfmomentsolve(EQ[chn],1), Chain[2](z)); ${\mathrm{gf}}_{\mathrm{chn}}:=-\frac{1}{-1\+2z}$ ${\mathrm{agf}}_{\mathrm{chn}}:=\frac{2z\left(\mathrm{sq}\+\mathrm{mul}\right)}{4z^2-4z\+1}$ (3.1.1.2) It is already known that there are $2^n$ binary strings of length n. You can do a series development to determine what agf[chn] looks like. >  avg_sum[chn]:=ncoeff(agf[chn],z,n); ${\mathrm{avg\_sum}}_{\mathrm{chn}}:=-\left(\mathrm{sq}\+\mathrm{mul}\right)2^n\+\left(\mathrm{sq}\+\mathrm{mul}\right)\left(n\+1\right)2^n$ (3.1.1.3) Thus, the average is their quotient. >  avg[chn]:= simplify(avg_sum[chn]/2^n, power); ${\mathrm{avg}}_{\mathrm{chn}}:=\mathrm{mul}n\+n\mathrm{sq}$ (3.1.1.4) Set a certain value for each squaring and multiplication. >  subs(sq=1, mul=1, avg[chn]); $2n$ (3.1.1.5) On average the binary method requires  $2{\log }_2\left(c\right)$ multiplications to calculate $x^c$, a stark improvement over c-1 the number required in brute force method. A Smarter Treatment of Addition Chains Use the observation that long chains of 1s are better handled with a division to improve the algorithm.  For example, $x^{15}\=\frac{x^{16}}{x}$ which, depending on the cost of a division, is more economical than the algorithm in the first example. If two 1s are encountered, assume that they are treated like a squaring followed by a division.  Represent an automaton which assigns costs based on state transition. For example, in a "1"-state, encountering a 1 implies at least two 1s in a row, hence, square. If it encounters a zero, simulate the division. An ochain is a binary chain with exactly one leading one. An oochain is a binary chain with at least 2 leading ones. >  GG[chn2] := {start = Prod(chain, one),         chain =  Union(Prod(zero, chain), Prod(one, ochain), Epsilon),         ochain = Union(Prod(zero, chain), Prod(one, oochain),Epsilon),         oochain = Union(Prod(zero, chain), Prod(one, oochain), Epsilon), zero=Atom, one=Atom}: AG[chn2]:={cost(start) = Prod(cost(chain), di),         cost(chain) = Union(Prod(sq, cost(chain)), Prod(sq, cost(ochain)), 0),         cost(ochain) = Union(Prod(sq+ml, cost(chain)),                              Prod(sq+ml, cost(oochain)),0),         cost(oochain) = Union(Prod(sq+ml, cost(chain)),                              Prod(sq, cost(oochain)),0) }: >  EQ[chn2]:=agfeqns(GG[chn2], AG[chn2], unlabeled, z, [[u, cost]]): As before, if you set u=1 and solve, the generating function for Chains is obtained. If you differentiate with respect to u and set u=1, the grand average generating function is obtained. >  gf[chn2]:=subs(agfmomentsolve(EQ[chn2],0), start(z)); agf[chn2]:=subs(agfmomentsolve(EQ[chn2],1), start[2](z)); ${\mathrm{gf}}_{\mathrm{chn2}}:=-\frac{z}{-1\+2z}$ ${\mathrm{agf}}_{\mathrm{chn2}}:=-\frac{z\left(\mathrm{ml}{z}^3-2\mathrm{ml}{z}^2\+2\mathrm{di}z-2\mathrm{sq}z-\mathrm{di}\right)}{{\left(-1\+2z\right)}^2}$ (3.1.2.1) Again, you can solve a recurrence to determine the coefficient. >  avg_sum[chn2]:= ncoeff(agf[chn2],z,n); ${\mathrm{avg\_sum}}_{\mathrm{chn2}}:=\mathrm{rsolve}\left(\left\{a\left(1\right)\=\mathrm{di}\,a\left(2\right)\=2\mathrm{sq}\+2\mathrm{di}\,a\left(3\right)\=8\mathrm{sq}\+2\mathrm{ml}\+4\mathrm{di}\,a\left(4\right)\=24\mathrm{sq}\+7\mathrm{ml}\+8\mathrm{di}\,a\left(n\right)\=4a\left(n-1\right)-4a\left(n-2\right)\right\}\,a\left(n\right)\right)$ (3.1.2.2) >  num[chn2]:= 2^(n-1); ${\mathrm{num}}_{\mathrm{chn2}}:=2^{n-1}$ (3.1.2.3) >   avg[chn2]:= expand(avg_sum[chn2]/num[chn2],n=infinity,2); ${\mathrm{avg}}_{\mathrm{chn2}}:=\frac{2\mathrm{rsolve}\left(\left\{a\left(1\right)\=\mathrm{di}\,a\left(2\right)\=2\mathrm{sq}\+2\mathrm{di}\,a\left(3\right)\=8\mathrm{sq}\+2\mathrm{ml}\+4\mathrm{di}\,a\left(4\right)\=24\mathrm{sq}\+7\mathrm{ml}\+8\mathrm{di}\,a\left(n\right)\=4a\left(n-1\right)-4a\left(n-2\right)\right\}\,a\left(n\right)\right)}{2^n}$ (3.1.2.4) Notice, asymptotically the divisions do not factor into the cost. Further, if you make the same assumption as before, that is, that squaring and multiplications are the same, >  subs(sq=ml, avg[chn2]); $\frac{2\mathrm{rsolve}\left(\left\{a\left(1\right)\=\mathrm{di}\,a\left(2\right)\=2\mathrm{ml}\+2\mathrm{di}\,a\left(3\right)\=10\mathrm{ml}\+4\mathrm{di}\,a\left(4\right)\=31\mathrm{ml}\+8\mathrm{di}\,a\left(n\right)\=4a\left(n-1\right)-4a\left(n-2\right)\right\}\,a\left(n\right)\right)}{2^n}$ (3.1.2.5) you notice a savings in the leading constant.

Symbolic Differentiation

In this example, you determine the cost of a symbolic differentiation algorithm. Limit the symbolic differentiation program to only expressions built from the variable x and constants 0 and 1 using addition, multiplication, and exponentiation.   The algorithm creates the expression trees associated with the differentiation and, the result is obtained by traversing the tree. The cost is proportional to the size of the resulting expression tree.  You can use an attribute grammar to model this cost.   Copy the Expressions The model simply copies the expression tree in question. >  GG[diff1]:={Exp = Union(csts,                   Prod(p, Exp, Exp), # addition                   Prod(m, Exp, Exp), # multiplication                   Prod(e, Exp)),     # exponentiation           csts=Union(zero, one, x),                   zero= Atom, one=  Atom, x= Atom,           p= Atom, m= Atom, e= Atom   }: >  AG[diff1]:={DSize(Exp) = Union(1,          # constants are of size 1                                      Prod(1, DSize(Exp), DSize(Exp)),                   # sum rule                                      Prod(3, size(Exp)+DSize(Exp), size(Exp)+DSize(Exp)),                   # product rule                   Prod(2, DSize(Exp)+size(Exp)))}:                   # exponential rule Next, determine the generating functions associated with the number of expressions and their grand average. >  EQNS[diff1]:= agfeqns(GG[diff1], AG[diff1], unlabeled, z, [[u, DSize]]): >  gf[diff1]:= subs(agfmomentsolve(EQNS[diff1], 0), Exp(z)); agf[diff1]:=subs(agfmomentsolve(EQNS[diff1], 1), Exp[2](z)); ${\mathrm{gf}}_{\mathrm{diff1}}:=-\frac{1}{4}\frac{z-1\+\sqrt{-23z^2-2z\+1}}{z}$ ${\mathrm{agf}}_{\mathrm{diff1}}:=\frac{1}{4}\frac{12z^2\sqrt{-23z^2-2z\+1}\+2z\sqrt{-23z^2-2z\+1}-34z^2-\sqrt{-23z^2-2z\+1}-3z\+1}{z\left(23z^2\+2z-1\right)}$ (3.2.1.1) The generating functions are nice enough to suit the standard tools in Maple for coefficient extraction. However, the asymptotic tools in algolib can determine a nice expression. In fact, you can deduce that the order of this algorithm is $0.8042175440n^{\frac{3}{2}}\+\mathrm{O}\left(n\right)$ and the variance is of order $0.0394740304n^3\+\mathrm{O}\left(1.n^{\frac{5}{2}}\right)$.

Dyck Paths

A Dyck path  is a sequence of unit diagonal movements (left-up or down-left) on the xy-plane starting from (0,0) such that the path never goes below the horizon, but at its end is exactly at the horizon. Put another way, they are 0-1 sequences that have the same number of 0s as 1s such that every prefix has at least as many 0s as 1s. They are in bijective correspondence with many things including binary trees, proper parenthetizations, nonintersecting chords joining 2n points on the circumference of a circle, and standard young tableau of shape (n, n). Refer to "Enumerative Combinatorics" exercise 6.19 for more (see references below).   Consider the area underneath a Dyck path. A standard decomposition of a Dyck path is into disjoint "mountains" where each mountain has at least one up movement and one down movement with some Dyck path between. The area of a Dyck path can be calculated recursively from this description. The area of the path is the sum of its mountains. The area of the mountain is the area of the base (equal to its length-1) plus the area of the nonbase part. >  GG[dpath]:= {Path= Sequence(Mountain), Mountain= Prod(up, Path, down), up= Atom, down = Epsilon}: AG[dpath]:= {Area(Path) = Sequence(Area(Mountain)), Area(Mountain) = Prod(0, Area(Path)+2*size(Path), 0)+1}: >  EQNS[dpath] :=agfeqns(GG[dpath], AG[dpath], unlabeled, z, [[u, Area]]); ${\mathrm{EQNS}}_{\mathrm{dpath}}:=\left[\mathrm{Path}\left(z\,u\right)\=\frac{1}{1-\mathrm{Mountain}\left(z\,u\right)}\,\mathrm{down}\left(z\,u\right)\=1\,\mathrm{up}\left(z\,u\right)\=zu\,\mathrm{Mountain}\left(z\,u\right)\=uz\mathrm{Path}\left(u^{2}z\,u\right)\right]$ (3.3.1) As before, solve these equations. >  gf[dpath]:= subs(agfmomentsolve(EQNS[dpath],0), Path(z)); agf[dpath]:= subs(agfmomentsolve(EQNS[dpath],1), Path[2](z)); ${\mathrm{gf}}_{\mathrm{dpath}}:=-\frac{1}{2}\frac{-1\+\sqrt{1-4z}}{z}$ ${\mathrm{agf}}_{\mathrm{dpath}}:=\frac{1}{2}\frac{\sqrt{1-4z}-1\+2z}{z\left(-1\+4z\right)}$ (3.3.2) >  gfseries(GG[dpath], unlabeled, z)[Path(z)]; series(agf[dpath],z,11);   $1\+z\+2z^2\+5z^3\+14z^4\+42z^5\+132z^6\+429z^7\+1430z^8\+4862z^9\+\mathrm{O}\left(z^{10}\right)$ $z\+6z^2\+29z^3\+130z^4\+562z^5\+2380z^6\+9949z^7\+41226z^8\+169766z^9\+\mathrm{O}\left(z^{10}\right)$ (3.3.3) The average area of a Dyck path of length 9 is >  169766/4862.; $34.91690662$ (3.3.4) The generating function should look familiar. It is the same as those for the variance of pathlength in binary trees.  This implies the exercise: find the bijection between binary trees and Dyck paths.

On the Number of Parts in a Partition

This is an example of a family of problems to which attribute grammars are well suited. Determine information about substructures within a structure. In this case, you want to learn about the parts of a partition. You can easily describe a partition as a set of parts, hence, determining information related to the parts is easily obtained.   The Average Number of Parts in a Partition A partition of a number n is an unordered collection positive integers less than or equal to n, which sum to n. For example, 1+1+3=5 indicates the partition of 5 into (1,1,3), a partition with 5 parts.   You can determine the generating function expression for the average number of parts in a partition. Model the parts as sequences of atoms. Thus, a partition is a set of such sequences. For each element in the set, count 1. Thus, in the following grammar the attribute Parts counts the number of parts in the partition. You can calculate the generating function. >  GG[part]:= {A= Set(Sequence(Z, card>0)), Z= Atom}: AG[part]:= {Parts(A)= Set(1)}: >  EQN[part]:= agfeqns(GG[part], AG[part], unlabeled, z, [[u, Parts]]): gf[part]:= subs(agfmomentsolve(EQN[part], 0), A(z)); ${\mathrm{gf}}_{\mathrm{part}}:={\ⅇ}^{\sum _{j_1\=1}^{\mathrm{\∞}}\frac{\frac{1}{-z^{j_1}\+1}-1}{j_1}}$ (3.4.1.1) Even if the generating function expression is awkward, you can compute multivariate series information. >  Series[part]:=agfseries(GG[part], AG[part], unlabeled, z, [[u, Parts]])[A(z,u)]; ${\mathrm{Series}}_{\mathrm{part}}:=1\+uz\+\left(u^2\+u\right)z^2\+\left(u^3\+u^2\+u\right)z^3\+\left(u^4\+u^3\+2u^2\+u\right)z^4\+\left(u^5\+u^4\+2u^3\+2u^2\+u\right)z^5\+\left(u^6\+u^5\+2u^4\+3u^3\+3u^2\+u\right)z^6\+\left(u^7\+u^6\+2u^5\+3u^4\+4u^3\+3u^2\+u\right)z^7\+\left(u^8\+u^7\+2u^6\+3u^5\+5u^4\+5u^3\+4u^2\+u\right)z^8\+\left(u^9\+u^8\+2u^7\+3u^6\+5u^5\+6u^4\+7u^3\+4u^2\+u\right)z^9\+\mathrm{O}\left(z^{10}\right)$ (3.4.1.2) Use this to calculate the grand average generating function. >  series1:=subs(u=1,diff(Series[part],u)); $\mathrm{series1}:=z\+3z^2\+6z^3\+12z^4\+20z^5\+35z^6\+54z^7\+86z^8\+128z^9\+\mathrm{O}\left(z^{10}\right)$ (3.4.1.3) The counting generating function. >  series2:=subs(u=1,Series[part]); $\mathrm{series2}:=1\+z\+2z^2\+3z^3\+5z^4\+7z^5\+11z^6\+15z^7\+22z^8\+30z^9\+\mathrm{O}\left(z^{10}\right)$ (3.4.1.4) From which, you can deduce that there are on average 128/30 =4.267 parts in a partition of 9. >  128./30; $4.266666667$ (3.4.1.5) >  seq(evalf(coeff(series1, z, i)/coeff(series2, z, i),2), i=0..9); $0.\,1.\,1.5\,2.\,2.4\,2.9\,3.2\,3.6\,3.9\,4.3$ (3.4.1.6) The last sequence here gives an indication of the rate of growth of the number of parts in a partition.

atomic, combstruct, combstruct[agfeqns], combstruct[agfmomentsolve], combstruct[agfseries], Generating functions 

A list of references related to automatic complexity analysis is available on the combstruct help page. These references contain the theoretical foundations of the program and examples of other applications, as well as references to attribute grammars with a focus on combinatorial aspects.

Flajoley, P.; Salvy, B.; and Zimmerman, P. "The Lambda-Upsilon-Omega: The 1989 Cookbook." INRIA Research Report, No. 1073. Available for download at http://algo.inria.fr/papers/bibgen/algobib.html.

Mishna, M. "Attribute Grammars and Automatic Complexity Analysis." Formal Power Series and Algebraic Combinatorics (FPSAC) 01 Conference Proceedings. (Also available as INRIA Research Report, no. 4643.)

Stanleyi, R. Enumerative Combinatorics. Vol. 2. Cambridge Press, 1997.