Needed computations shortcutting needed steps

Sergio Antoy, Jacob Johannsen, Steven Libby

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


We define a compilation scheme for a constructor-based, strongly-sequential, graph rewriting system which shortcuts some needed steps. The object code is another constructor-based graph rewriting system. This system is normalizing for the original system when using an innermost strategy. Consequently, the object code can be easily implemented by eager functions in a variety of programming languages. We modify this object code in a way that avoids total or partial construction of the contracta of some needed steps of a computation. 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
Title of host publicationElectronic Proceedings in Theoretical Computer Science, EPTCS
Number of pages15
PublisherOpen Publishing Association
Publication date2015
Publication statusPublished - 2015
Event8th International Workshop on Computing with Terms and Graphs, TERMGRAPH 2014 - Vienna, Austria
Duration: 13 Jul 2014 → …


Conference8th International Workshop on Computing with Terms and Graphs, TERMGRAPH 2014
Period13/07/2014 → …


Dive into the research topics of 'Needed computations shortcutting needed steps'. Together they form a unique fingerprint.

Cite this