{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19122"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19122","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Categorization and analyzing linked structures","abstract":"In this thesis, we categorize linked structures and linked substructures each into four groups based on two attributes, sharing and cycles. We show that these two attributes can be determined at compile-time by augmenting any store-based analysis with heap reference counts and the missing link property. An analysis, which has the form of an abstract interpretation, is defined and implemented with the program generator Z1. The language analyzed is a low-level intermediate form in which there is no user-level type information. This fact makes the analysis applicable to languages like C and C++, for which type casting and type violations are frequent.","abstract_html":"In this thesis, we categorize linked structures and linked substructures each into four groups based on two attributes, sharing and cycles. We show that these two attributes can be determined at compile-time by augmenting any store-based analysis with heap reference counts and the missing link property. An analysis, which has the form of an abstract interpretation, is defined and implemented with the program generator Z1. The language analyzed is a low-level intermediate form in which there is no user-level type information. This fact makes the analysis applicable to languages like C and C++, for which type casting and type violations are frequent.","abstract_has_math":false,"creators":["Tsai, Mei-Chin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Harrison, Williams Ludwell, III,"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T11:57:37Z","date_published":"2011-05-07T11:57:37Z","updated_at":"2026-07-22T22:25:12Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1994 Tsai, Mei-Chin"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9512576","(UMI)AAI9512576"],"render_values":[{"text":"AAI9512576","href":null,"code":true},{"text":"(UMI)AAI9512576","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19122","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Harrison, Williams Ludwell, III,"]},{"key":"dc:creator","label":"Author","values":["Tsai, Mei-Chin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T11:57:37Z","10000-01-01","1994"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1994 Tsai, Mei-Chin"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9512576","(UMI)AAI9512576","http://hdl.handle.net/2142/19122"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In this thesis, we categorize linked structures and linked substructures each into four groups based on two attributes, sharing and cycles. We show that these two attributes can be determined at compile-time by augmenting any store-based analysis with heap reference counts and the missing link property. An analysis, which has the form of an abstract interpretation, is defined and implemented with the program generator Z1. The language analyzed is a low-level intermediate form in which there is no user-level type information. This fact makes the analysis applicable to languages like C and C++, for which type casting and type violations are frequent.","A set of programs that create and manipulate linked structures is analyzed. The results show that the analysis is able to correctly recognize a variety of linked data structures, such as radix trees and binary search trees, and substructures, such as those defined by down and next pointer fields in meshes.","Made available in DSpace on 2011-05-07T11:57:37Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9512576.pdf: 4543311 bytes, checksum: 74c2a0f295ccf031c36f68c160716952 (MD5) Previous issue date: 1994","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:34:48Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:13:28-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Categorization and analyzing linked structures"]}]}],"canonical_facts":{"dc:contributor":["Harrison, Williams Ludwell, III,"],"dc:creator":["Tsai, Mei-Chin"],"dc:date":["2011-05-07T11:57:37Z","10000-01-01","1994"],"dc:description":["In this thesis, we categorize linked structures and linked substructures each into four groups based on two attributes, sharing and cycles. We show that these two attributes can be determined at compile-time by augmenting any store-based analysis with heap reference counts and the missing link property. An analysis, which has the form of an abstract interpretation, is defined and implemented with the program generator Z1. The language analyzed is a low-level intermediate form in which there is no user-level type information. This fact makes the analysis applicable to languages like C and C++, for which type casting and type violations are frequent.","A set of programs that create and manipulate linked structures is analyzed. The results show that the analysis is able to correctly recognize a variety of linked data structures, such as radix trees and binary search trees, and substructures, such as those defined by down and next pointer fields in meshes.","Made available in DSpace on 2011-05-07T11:57:37Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9512576.pdf: 4543311 bytes, checksum: 74c2a0f295ccf031c36f68c160716952 (MD5) Previous issue date: 1994","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:34:48Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:13:28-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9512576","(UMI)AAI9512576","http://hdl.handle.net/2142/19122"],"dc:language":["eng"],"dc:rights":["Copyright 1994 Tsai, Mei-Chin"],"dc:subject":["Computer Science"],"dc:title":["Categorization and analyzing linked structures"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:12Z"}