English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  How to realize LSE narrowing

Werner, A., Bockmayr, A., & Krischer, S. (1998). How to realize LSE narrowing. New Generation Computing, 16(4), 397-434.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Werner, Andreas, Author
Bockmayr, Alexander1, Author           
Krischer, Stefan, Author
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Content

show
hide
Free keywords: -
 Abstract: Narrowing is a complete unification procedure for equational theories defined by canonical term rewriting systems. It is also the operational semantics of various logic and functional programming languages. In an earlier paper, we introduced the LSE narrowing strategy which is complete for arbitrary canonical rewriting systems and optimal in the sense that two different LSE narrowing derivations cannot generate the same narrowing substitution. LSE narrowing improves all previously known strategies for the class of arbitrary canonical systems. LSE narrowing detects redundant derivations by reducibility tests. According to their definition, LSE narrowing steps seem to be very expensive, because a large number of subterms has to be tested. In this paper, we show that many of these subterms are identical. We describe how left-to-right basic occurrences can be used to identify and exclude these identical subterms. This way, we can drastically reduce the number of subterms that have to be tested. Based on these theoretical results, we develop an efficient implementation of LSE narrowing.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-121998
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 519655
Other: Local-ID: C1256104005ECAFC-E58551BD48DDDA7BC125668E003266EE-WernerBockmayrKrischer98
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: New Generation Computing
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 16 (4) Sequence Number: - Start / End Page: 397 - 434 Identifier: ISSN: 0288-3635