{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/21931"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/21931","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Implementation techniques for rewriting and narrowing","abstract":"Rewrite systems are directed equations that can be used to compute by repeatedly rewriting an initial term until a final form is obtained. Such systems provide a nondeterministic programming language having convenient mathematical properties. Programs are easy to understand, as they have very simple syntax and semantics, based on equalities, with no explicit control. By allowing variables within the initial term, the term may be thought of as a logical query. It is possible to solve queries by narrowing, i.e. using the left-hand sides of rules to identify subterms with instances to which rules apply, and repeating the process until instantiations of the variables are constructed that can be shown by rewriting to satisfy the query.","abstract_html":"Rewrite systems are directed equations that can be used to compute by repeatedly rewriting an initial term until a final form is obtained. Such systems provide a nondeterministic programming language having convenient mathematical properties. Programs are easy to understand, as they have very simple syntax and semantics, based on equalities, with no explicit control. By allowing variables within the initial term, the term may be thought of as a logical query. It is possible to solve queries by narrowing, i.e. using the left-hand sides of rules to identify subterms with instances to which rules apply, and repeating the process until instantiations of the variables are constructed that can be shown by rewriting to satisfy the query.","abstract_has_math":false,"creators":["Josephson, Norman Alan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Dershowitz, Nachum"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T13:23:34Z","date_published":"2011-05-07T13:23:34Z","updated_at":"2026-07-22T22:25:18Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1989 Josephson, Norman Alan"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI8924855","(UMI)AAI8924855"],"render_values":[{"text":"AAI8924855","href":null,"code":true},{"text":"(UMI)AAI8924855","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/21931","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Dershowitz, Nachum"]},{"key":"dc:creator","label":"Author","values":["Josephson, Norman Alan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:23:34Z","10000-01-01","1989"]},{"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 1989 Josephson, Norman Alan"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI8924855","(UMI)AAI8924855","http://hdl.handle.net/2142/21931"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Rewrite systems are directed equations that can be used to compute by repeatedly rewriting an initial term until a final form is obtained. Such systems provide a nondeterministic programming language having convenient mathematical properties. Programs are easy to understand, as they have very simple syntax and semantics, based on equalities, with no explicit control. By allowing variables within the initial term, the term may be thought of as a logical query. It is possible to solve queries by narrowing, i.e. using the left-hand sides of rules to identify subterms with instances to which rules apply, and repeating the process until instantiations of the variables are constructed that can be shown by rewriting to satisfy the query.","In this dissertation, we explore a class of optimizations relating to the repeated rewriting or normalization of a term. By maintaining more and more detailed information about the rewriting process, successive refinements of a basic normalization algorithm are possible which accelerate the discovery of a simplest form at the expense of the space required to store the information about the computation. In addition, we describe implementation techniques for enforcing an eager rewriting/lazy narrowing approach within the context of these optimizations. Rather than backtracking over narrowing steps to capture all solutions to a query, we demonstrate structure sharing techniques that allow us to make use of shared computation paths during the enumeration of solutions. We investigate extensions to the methods that allow us to handle conditional rules. An implementation, R scITE, is described and its performance on several examples is demonstrated.","Made available in DSpace on 2011-05-07T13:23:34Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 8924855.pdf: 4500722 bytes, checksum: 4ea8a3eb90997777cef01b217fb40f4c (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:54:10Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:25:08-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":["Implementation techniques for rewriting and narrowing"]}]}],"canonical_facts":{"dc:contributor":["Dershowitz, Nachum"],"dc:creator":["Josephson, Norman Alan"],"dc:date":["2011-05-07T13:23:34Z","10000-01-01","1989"],"dc:description":["Rewrite systems are directed equations that can be used to compute by repeatedly rewriting an initial term until a final form is obtained. Such systems provide a nondeterministic programming language having convenient mathematical properties. Programs are easy to understand, as they have very simple syntax and semantics, based on equalities, with no explicit control. By allowing variables within the initial term, the term may be thought of as a logical query. It is possible to solve queries by narrowing, i.e. using the left-hand sides of rules to identify subterms with instances to which rules apply, and repeating the process until instantiations of the variables are constructed that can be shown by rewriting to satisfy the query.","In this dissertation, we explore a class of optimizations relating to the repeated rewriting or normalization of a term. By maintaining more and more detailed information about the rewriting process, successive refinements of a basic normalization algorithm are possible which accelerate the discovery of a simplest form at the expense of the space required to store the information about the computation. In addition, we describe implementation techniques for enforcing an eager rewriting/lazy narrowing approach within the context of these optimizations. Rather than backtracking over narrowing steps to capture all solutions to a query, we demonstrate structure sharing techniques that allow us to make use of shared computation paths during the enumeration of solutions. We investigate extensions to the methods that allow us to handle conditional rules. An implementation, R scITE, is described and its performance on several examples is demonstrated.","Made available in DSpace on 2011-05-07T13:23:34Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 8924855.pdf: 4500722 bytes, checksum: 4ea8a3eb90997777cef01b217fb40f4c (MD5) Previous issue date: 1989","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:54:10Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:25:08-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":["AAI8924855","(UMI)AAI8924855","http://hdl.handle.net/2142/21931"],"dc:language":["eng"],"dc:rights":["Copyright 1989 Josephson, Norman Alan"],"dc:subject":["Computer Science"],"dc:title":["Implementation techniques for rewriting and narrowing"],"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:18Z"}