Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Programming Logics Group     Display Documents



ID: 519529.0, MPI für Informatik / Programming Logics Group
A Needed Narrowing Strategy
Authors:Antoy, Sergio; Echahed, Rachid; Hanus, Michael
Language:English
Publisher:ACM
Place of Publication:New York, USA
Date of Publication (YYYY-MM-DD):1994
Title of Proceedings:Proceedings of the 21st ACM Symposium on Principles of Programming Languages (POPL'94)
Start Page:268
End Page:279
Place of Conference/Meeting:Portland, USA
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
1994
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:Narrowing is the operational principle of languages that integrate functional
and logic programming. We propose a notion of a needed narrowing step that, for
inductively sequential rewrite systems, extends the Huet and Levy 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 independent
unifiers, and is efficiently implemented by pattern matching.
Last Change of the Resource (YYYY-MM-DD):2010-03-12
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Andreas Podelski
Affiliations:MPI für Informatik/Programming Logics Group
Identifiers:LOCALID:C1256104005ECAFC-62AE0D6224F5F524C12561440062210B-...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.