combstruct[agfeqns] - find the system of generating function equations associated with an attribute grammar
combstruct[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 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, would be a generating function for . These two functions, agfeqns and agfseries, determine the equations in terms of other nonterminals and specify the series for the generating functions, respectively.
|
•
|
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.
|
•
|
Each attribute must be marked by a single, unique variable.
|
|
|
Examples
|
|
>
|
|
For example, a labeled binary tree is a node or a node and two subtrees.
>
|
|
One can use attributes to count the number of leaves.
>
|
|
>
|
|
| (1) |
For example, the series up to order 10 indicates that there are five trees with 7 nodes and 4 leaves.
>
|
|
| (2) |
The internal path length, or sum of distances from nodes to the root, can be defined recursively.
>
|
|
>
|
|
| (3) |
This system can be solved and the average values attained.
|
|