25th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2015)
Logics and Meanings of Programs, Mathematical Logic and Formal Languages, Artificial Intelligence (incl. Robotics), Discrete Mathematics in Computer Science
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.
Antoy, Sergio and Jost, Andy, "Compiling Collapsing Rules in Certain Constructor Systems" (2015). Computer Science Faculty Publications and Presentations. 137.