Short Encodings of Evolving Combinatorial Structures
A derivation in a transformational system such as a graph grammar is redundant in the sense that the exact order of the transformations does not affect the final outcome; all that matters is that each transformation, when applied, is applied to the correct substructure. By taking advantage of this redundancy, we are able to develop an efficient encoding scheme for such derivations. This encoding scheme has a number of diverse applications. It can be used in efficient enumeration of combinatorial objects or for compact representation of program and data structure transformations. It can also be used to derive lower bands on lengths of derivations. We show for example, that ohms(nlogn) applications of the associative and commutative laws are required to transform an n-variable expression over a binary associative, commutative operation into any equivalent expression. Similarly, we show that ohms(nlogn) 'diagonal flips' are required to transform one n-vertex numbered triangulated planar graph into any other. Both of these lower bounds are tight.