Published In

25th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2015)

Document Type

Post-Print

Publication Date

7-13-2015

Subjects

Logics and Meanings of Programs, Mathematical Logic and Formal Languages, Artificial Intelligence (incl. Robotics), Discrete Mathematics in Computer Science

Abstract

The implementation of functional logic languages by means of graph rewriting requires a special handling of collapsing rules. Recent advances about the notion of a needed step in some constructor systems offer a new approach to this problem. We present two results: a transformation of a certain class of constructor-based rewrite systems that eliminates collapsing rules, and a rewrite-like relation that takes advantage of the absence of collapsing rules. We formally state and prove the correctness of these results. When used together, these results simplify without any loss of efficiency an implementation of graph rewriting and consequently of functional logic computations.

Description

Paper presented at the 25th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2015), Siena, IT, July 13-15, 2015. Subsequently published by Springer.

DOI

10.1007/978-3-319-27436-2_4

Persistent Identifier

http://archives.pdx.edu/ds/psu/16598

Available for download on Friday, February 10, 2017

Share

COinS