Abstract. A derivation in a transformational system such as a graph grammar may be redundant in the sense that the exact order of the transformations may not &ed 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 can 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 objeds or for compact representation of program and data structure transformations. It can also be used to derive lower bounds on lengths of derivations. It is shown, for example, that n(n1ogn) applications of the associative and commutative laws are required in the worst case to transform an n-variable expression over a binary associative, commutative operation into some other equivalent expression. Similarly, it is shown that n(n1ogn) "diagonal flips" are required in the worst case to transform one n-vertex numbered triangulated planar graph into some other one. Both of these lower bounds have matching upper bounds. An O(n log n) upper bound for associative, commutative operations was known previously, whereas here an O(n log n) upper bound for diagonal flips is obtained.
Sleator et al. REF proved that O(n log n) flips are sufficient to transform one labelled maximal planar graph with n vertices into another with the same vertices, and Ω(n log n) flips are sometimes necessary.
SHORT ENCODINGS OF EVOLVING STRUCTURES*
SIAM J. Discrete Math.
SIAM J. Discrete Math.
Mathematics Computer Science