agfeqns - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

combstruct

 agfeqns
 find the system of generating function equations associated with an attribute grammar
 agfseries
 find the series solution of a system of generating function equations associated with an attribute grammar

 Calling Sequence agfeqns(spec, a_spec, typ, var, att_list) agfseries(spec, a_spec, typ, var, att_list)

Parameters

 spec - combinatorial specification a_spec - specification of attribute grammar associated with spec typ - labeling type; 'labeled' or 'unlabeled' var - main (size) variable in the generating function att_list - list of lists associating attribute names with variables

Description

 • These functions, agfeqns and agfseries, form the attribute grammar analogues to combstruct[gfeqns], and combstruct[gfseries].  For details on specifications, see combstruct and combstruct[specification].
 • These functions involve multivariate generating function equations which count the objects, as described in the specification spec, and properties of the structures, as defined in the attribute grammar, a_spec.
 Each nonterminal in the grammar is associated with a generating function which is named with the name of the structure. For example, $A\left(z,u\right)$ would be a generating function for $A$.  These two functions, agfeqns and agfseries, determine the equations in terms of other nonterminals and specify the series for the generating functions, respectively.
 • For example, in an unlabeled system with structure $A$ and attributes ${f}_{1}$ and ${f}_{2}$, the multivariate generating function is defined as $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)}$.
 • Any number of attributes is allowable, but no user-defined attribute can be marked by the parameter var.
 • If the objects are labeled, the exponential generating functions are produced. If the objects are unlabeled, ordinary generating functions are used.
 • The attribute, size, is used for the property pertaining to the number of atoms. It can be referenced in another attribute, but not redefined.
 • If no rule is defined for a given attribute structure pair, a default recursive rule is used. For example, $A=\mathrm{Union}\left(B,C,E\right)$ and the attribute $f$ imply a default attribute specification of $f\left(A\right)=\mathrm{Union}\left(f\left(B\right),f\left(C\right),f\left(E\right)\right)$.
 • Each attribute must be marked by a single, unique variable.

Examples

 > $\mathrm{with}\left(\mathrm{combstruct}\right):$

For example, a labeled binary tree is a node or a node and two subtrees.

 > $\mathrm{tree}≔\left\{T=\mathrm{Union}\left(N,\mathrm{Prod}\left(N,T,T\right)\right),N=\mathrm{Atom}\right\}:$

One can use attributes to count the number of leaves.

 > $\mathrm{l_tree}≔\left\{\mathrm{leaf}\left(T\right)=\mathrm{Union}\left(1,\mathrm{Prod}\left(0,\mathrm{leaf}\left(T\right),\mathrm{leaf}\left(T\right)\right)\right)\right\}:$
 > $\mathrm{agfeqns}\left(\mathrm{tree},\mathrm{l_tree},\mathrm{unlabeled},z,\left[\left[u,\mathrm{leaf}\right]\right]\right)$
 $\left[{N}{}\left({z}{,}{u}\right){=}{z}{}{u}{,}{T}{}\left({z}{,}{u}\right){=}{z}{}{u}{+}{z}{}{{T}{}\left({z}{,}{u}\right)}^{{2}}\right]$ (1)

For example, the series up to order 10 indicates that there are five trees with 7 nodes and 4 leaves.

 > $\mathrm{Order}≔10:$$\mathrm{agfseries}\left(\mathrm{tree},\mathrm{l_tree},\mathrm{unlabeled},z,\left[\left[u,\mathrm{leaf}\right]\right]\right)$
 ${table}{}\left(\left[{T}{}\left({z}{,}{u}\right){=}{u}{}{z}{+}{{u}}^{{2}}{}{{z}}^{{3}}{+}{2}{}{{u}}^{{3}}{}{{z}}^{{5}}{+}{5}{}{{u}}^{{4}}{}{{z}}^{{7}}{+}{14}{}{{u}}^{{5}}{}{{z}}^{{9}}{+}{O}{}\left({{z}}^{{11}}\right){,}{N}{}\left({z}{,}{u}\right){=}{u}{}{z}\right]\right)$ (2)

The internal path length, or sum of distances from nodes to the root, can be defined recursively.

 > $\mathrm{pl_tree}≔\left\{\mathrm{path}\left(T\right)=\mathrm{Union}\left(0,\mathrm{Prod}\left(0,\mathrm{size}\left(T\right)+\mathrm{path}\left(T\right),\mathrm{size}\left(T\right)+\mathrm{path}\left(T\right)\right)\right)\right\}:$
 > $\mathrm{agfeqns}\left(\mathrm{tree},\mathrm{pl_tree},\mathrm{unlabeled},z,\left[\left[u,\mathrm{path}\right]\right]\right)$
 $\left[{N}{}\left({z}{,}{u}\right){=}{z}{}{u}{,}{T}{}\left({z}{,}{u}\right){=}{z}{+}{z}{}{{T}{}\left({z}{}{u}{,}{u}\right)}^{{2}}\right]$ (3)

This system can be solved and the average values attained.