Needed computations shortcutting needed steps

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



  • Sergio Antoy, Portland State University
  • ,
  • Jacob Johannsen
  • Steven Libby, Portland State University

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 year2015
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
Periode13/07/2014 → …

See relations at Aarhus University Citationformats

ID: 97983625