NDLI: Short Encodings of Evolving Structures

Please wait, while we are loading the content...

Short Encodings of Evolving Structures

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Trajan, Robert E. Thurston, William P. Sleator, Daniel D.
Copyright Year	1992
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 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 objects 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 $\Omega ( n \log n )$ 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 $\Omega ( n\log 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 $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.
Starting Page	428
Ending Page	450
Page Count	23
File Format	PDF
ISSN	08954801
DOI	10.1137/0405034
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	3
Volume Number	5
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-08-08
Access Restriction	Subscribed
Subject Keyword	graph transformations triangulation graph grammar commutativity diagonal flips associativity
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in