Needed Computations Shortcutting Needed Steps

Sergio Antoy, Jacob Johannsen, Steven Libby

Research output: Contribution to conferencePaperResearchpeer-review

162 Downloads (Pure)


We define a compilation scheme for a constructor-based strongly-sequential graph rewriting system
which shortcuts some needed steps. The result of this compilation is another constructor-based graph
rewriting system that is normalizing for the original system when using an innermost strategy. We
then modify the resulting rewrite sytem in a way that avoids totally or partially the construction of
of some needed steps of a computation. The resulting rewrite system can be easily
implemented by eager functions in a variety of programming languages. When computing normal
forms in this way, both memory consumption and execution time are reduced compared to ordinary
rewriting computations in the original system
Original languageEnglish
Publication date2014
Number of pages5
Publication statusPublished - 2014
EventInternational Workshop on Computing with Terms and Graphs - Vienna, Austria
Duration: 13 Jul 201413 Jul 2014
Conference number: 8


WorkshopInternational Workshop on Computing with Terms and Graphs

Cite this