combstruct - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Combinatorial Structures : combstruct/agfeqns

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

Parameters

Description

Examples

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, Az,u 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 f1 and f2, the multivariate generating function is defined as Az,q1,q2=Azaq1f[1]aq2f[2]a.

• 

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=UnionB,C,E and the attribute f imply a default attribute specification of fA=UnionfB,fC,fE.

• 

Each attribute must be marked by a single, unique variable.

Examples

withcombstruct:

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

treeT=UnionN,ProdN,T,T,N=Atom:

One can use attributes to count the number of leaves.

l_treeleafT=Union1,Prod0,leafT,leafT:

agfeqnstree,l_tree,unlabeled,z,u,leaf

Nz,u=zu,Tz,u=zu+zTz,u2

(1)

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

Order10:agfseriestree,l_tree,unlabeled,z,u,leaf

tableNz,u=uz,Tz,u=uz+u2z3+2u3z5+5u4z7+14u5z9+Oz11

(2)

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

pl_treepathT=Union0,Prod0,sizeT+pathT,sizeT+pathT:

agfeqnstree,pl_tree,unlabeled,z,u,path

Nz,u=zu,Tz,u=z+zTzu,u2

(3)

This system can be solved and the average values attained.

See Also

combstruct

combstruct[agfmomentsolve]

combstruct[gfseries]

combstruct[gfsolve]

combstruct[specification]

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam