Wednesday, March 13, 2013

Algebraic combinatorics

A set of transformations on a data structure forms a transformation monoid. Place forms are a special type of transformation monoid. Another important type of transformation monoid is a permutation group. The permutation groups arise in combinatorics as the automorphism groups of graphs and various other discrete data structures such as lists.

The set of transformation monoids can be partially ordered to form a lattice. Transformation monoids that are disjoint with respect to one another and that commute with all the operations contained in each other set are independent of one another. Each transformation monoid of the cartesian product of zero or more independent transformation monoids.

By understanding transformational independence we can begin to develop an understanding of parallelism because independent operations can be run in parallel. We can also version independent objects separately to implement fine grained versioning.

No comments:

Post a Comment