Abstrakt. En härledning i ett omvandlingssystem såsom en graf grammatik kan vara överflödig i den meningen att den exakta ordningen av omvandlingarna kanske inte & det slutliga resultatet; allt som betyder något är att varje omvandling, när den tillämpas, tillämpas på rätt understruktur. Genom att dra nytta av denna redundans kan vi utveckla ett effektivt kodningssystem för sådana derivat. Detta kodningssystem har ett antal olika tillämpningar. Det kan användas i effektiv uppräkning av kombinatoriska objeds eller för kompakt representation av program- och datastrukturomvandlingar. Det kan också användas för att härleda lägre gränser på längder av härledning. Det visas till exempel att n(n1ogn) tillämpningar av associativa och pendlande lagar krävs i värsta fall för att omvandla ett n-variabelt uttryck över en binär associativ, pendlande operation till något annat likvärdigt uttryck. På samma sätt visas att n(n1ogn) "diagonal flips" krävs i värsta fall för att omvandla en n-vertex numrerade triangulated planar diagram till någon annan. Båda dessa nedre gränser har motsvarande övre gränser. En O(n log n) övre gräns för associativa, pendlande operationer var känd tidigare, medan en O(n log n) övre gräns för diagonala flips erhålls här.
Sleator m.fl. REF visade att O(n log n) flips är tillräckliga för att omvandla en märkt maximal planar graf med n hörn till en annan med samma hörn, och  på (n log n) flips är ibland nödvändiga.
SHORT ENCODINGS OF EVOLVING STRUCTURES*
{'venue': 'SIAM J. Discrete Math.', 'journal': 'SIAM J. Discrete Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}