Grammar Specification of a Combinatorial Class

Description


•

A combinatorial class is either an elementary class, or is built from simpler classes with "constructors." The elementary classes are Epsilon, which represents an object of size zero, and Atom, which represents an object of size one. The available constructors are listed in the following table.



Epsilon

object of size 0

Atom

object of size 1 (Z is a predefined atom)

Union(A,B,...)

disjointunion of the classes A,B, ...

Prod(A,B,...)

partitional product of the classes A, B, ...

Set(A)

all sets with repetitions whose elements are in A

PowerSet(A)

all sets without repetitions whose elements are in A

Sequence(A)

all sequences of elements of A

Cycle(A)

all directed cycles of elements of A

Subst(A,B)

Bobjects whose atoms are replaced by Aobjects






None of these constructors accept an object that generates Epsilon as an argument. In some cases, no cardinality restriction or with any constructor but PowerSet, such a grammar generates an infinite number of objects of size 0, whereas this system is for classes with a finite number of members of each size.


In the others, PowerSet or or , while there are only a finite number of objects of size 0, the current system does not handle grammars with such Epsilon productions.


When the labeling type is 'labeled'.




nonplane trees


plane binary trees


plane general trees


permutations


set partitions


nonplane ternary trees


hierarchies


3balanced hierarchies


surjections


functional graphs






When the labeling type is 'unlabeled'.




integer partition


binary sequences


necklaces


rooted unlabeled trees


nonplane binary trees


nonplane ternary trees


unlabeled hierarchies


random mappings patterns


23 trees


integer partitions without


repetition





•

It is possible to use Epsilon as a way of marking certain objects without affecting their size.

•

There are also predefined structures, for example, combinations, built into the system. For more information, see combstruct[structures].



Examples


>


Generate words on two letters of the form .
>


>


 (1) 
If you do not need the derivation structure, remove it.
>


 (2) 
To model series and parallel circuits of resistors, a parallel circuit is made up of two or more resistors in series, and a series circuit is made up of two or more parallel circuits.
>


>


 (3) 
However, you cannot tell from this answer which resistors are in series and which are in parallel. In this case, you obtain more information about the derivation by using Epsilon tags.
>


>


 (4) 
Since Epsilon has size 0, taking the product with Epsilon does not change the number of objects of each size.

