Please use this identifier to cite or link to this item:
|Basic Narrowing Revisited
|Year of Publication:
|Place of publication:
|004 Computer science, internet
|In this paper we study basic narrowing as a method for solving equations in the initial algebra speciﬁed by a ground conﬂuent 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 uniﬁcation. 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 sufﬁce for a complete solution procedure. Failure rules detect inconsistent parts of the search space. Simpliﬁcation 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 simpliﬁcation 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 speciﬁc 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:
|SEKI-Report / Deutsches Forschungszentrum für Künstliche Intelligenz, DFKI [ISSN 1437-4447]
|Date of registration:
|Es fehlen S.13 und S.15.
|SE - Sonstige Einrichtungen
|SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
|SE - Sonstige
|SciDok - Der Wissenschaftsserver der Universität des Saarlandes
Files for this record:
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.