Please use this identifier to cite or link to this item: doi:10.22028/D291-39847
Title: Basic Narrowing Revisited
Author(s): Nutt, Werner
Réty, Pierre
Smolka, Gert
Language: English
Year of Publication: 1987
Place of publication: Kaiserslautern
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: In this paper we study basic narrowing as a method for solving equations in the initial algebra specified by a ground confluent and terminating term rewriting system. Since we are interested in equation solving, we don’t study basic narrowing as a reduction relation on terms but consider immediately its reformulation as an equation solving rule. This reformulation leads to a technically simpler presentation and reveals that the essence of basic narrowing can be captured without recourse to term unification. We present an equation solving calculus that features three classes of rules. Resolution rules, whose application is don’t care nondeterministic, are the basic rules and suffice for a complete solution procedure. Failure rules detect inconsistent parts of the search space. Simplification rules, whose application is don’t care nondeterministic, enhance the power of the failure rules and reduce the number of necessary don’t know steps. Three of the presented simplification rules are new. The rewriting rule allows for don’t care nondeterministic rewriting and thus yields a marriage of basic and normalizing narrowing. The safe blocking rule is specific to basic narrowing and is particulary useful in conjunction with the rewriting rule. Finally, the unfolding rule allows for a variety of search strategies that reduce the number of don’t know alternatives that need to be explored.
Link to this record: urn:nbn:de:bsz:291--ds-398476
Series name: SEKI-Report / Deutsches Forschungszentrum für Künstliche Intelligenz, DFKI [ISSN 1437-4447]
Series volume: 87,7
Date of registration: 15-Jun-2023
Notes: Es fehlen S.13 und S.15.
Faculty: SE - Sonstige Einrichtungen
Department: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Professorship: SE - Sonstige
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
SEKI-REPORT-SR-87-07_Nutt-Réty-Smolka_Basic-Narrowing-Revisited.pdf1,98 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.