- 著者
- Daniel D.K. Sleator, Robert D. Tarjan, William P. Thurston
- タイトル
- Short Encoding of Evolving Structures
- 日時
- Dec 1991
- 概要
- 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.
- カテゴリ
- CMUTR

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