COMPUTER SCIENCE COLLOQUIUM

A Finite Representation of the Narrowing Space and its Application

Naoki Nishida Graduate School of Information Science Nagoya University, Japan

Tuesday, 11 March, 2014 at 14:15 IMADA's Seminar Room

ABSTRACT

Narrowing basically extends rewriting by allowing free variables in terms and by replacing matching with unification. As a consequence, the search space of narrowing becomes usually infinite, as in logic programming.

In this talk, we introduce the use of some operators that allow one to always produce a finite data structure that still represents all the narrowing derivations. Furthermore, we extract from this data structure a novel, compact equational representation of the (possibly infinite) answers computed by narrowing for a given initial term. Both the finite data structure and the equational representation of the computed answers might be useful in a number of areas, like program comprehension, static analysis, program transformation, etc.

Host: Peter Schneider-Kamp

---

SDU HOME | IMADA HOME | Previous Page

---

Daniel Merkle