Loading...
Please wait, while we are loading the content...
Similar Documents
A Needed Narrowing Strategy (1994)
| Content Provider | CiteSeerX |
|---|---|
| Author | Hanus, Michael Echahed, Rachid Antoy, Sergio |
| Abstract | The narrowing relation over terms constitutes the basis of the most important operational semantics of languages that integrate functional and logic programming paradigms. It also plays an important role in the definition of some algorithms of unification modulo equational theories which are defined by confluent term rewriting systems. Due to the inefficiency of simple narrowing, many refined narrowing strategies have been proposed in the last decade. This paper presents a new narrowing strategy which is optimal in several respects. For this purpose we propose a notion of a needed narrowing step that, for inductively sequential rewrite systems, extends the Huet and Lévy notion of a needed reduction step. We define a strategy, based on this notion, that computes only needed narrowing steps. Our strategy is sound and complete for a large class of rewrite systems, is optimal w.r.t. the cost measure that counts the number of distinct steps of a derivation, computes only incomparable and disjoint unifiers, and is efficiently implemented by unification. |
| File Format | |
| Journal | Journal of the ACM |
| Journal | JOURNAL OF THE ACM |
| Publisher Date | 1994-01-01 |
| Access Restriction | Open |
| Subject Keyword | Narrowing Relation Needed Narrowing Strategy Important Operational Semantics Last Decade Reduction Step Important Role Equational Theory Rewrite System Simple Narrowing Large Class Vy Notion Narrowing Step Needed Narrowing Step Logic Programming Paradigm Several Respect Distinct Step Sequential Rewrite System Cost Measure Disjoint Unifiers New Narrowing Strategy Confluent Term |
| Content Type | Text |
| Resource Type | Article |
