Category: CMUTR
Institution: Department of Computer Science, Carnegie
        Mellon University
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 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 bounds on length of 
        derivations.
        We show for example that OMEGA(n long n) applications of the 
        associative and communicative 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, we show that OMEGA (n long n)"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 OMICRON (n long n) upper bound for associative, commutative 
        operations was known previously, whereas we obtain here an
        OMICRON (n long n) upper bound for diagonal flips.
        
Number: CMU-CS-91-206
Bibtype: TechReport
Month: Dec
Author: Daniel D.K. Sleator
        Robert D. Tarjan
        William P. Thurston
Title: Short Encoding of Evolving Structures
Year: 1991
Address: Pittsburgh, PA
Super: @CMUTR