Needed Computations Shortcutting Needed Steps

Research output: Contribution to conferencePaperResearchpeer-review

Documents

  • paper

    Submitted manuscript, 165 KB, PDF document

  • Sergio Antoy, Computer Science Dept., Portland State University, Portland, OR, United States
  • Jacob Johannsen
  • Steven Libby, Computer Science Dept., Portland State University, Portland, OR, United States
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
the
contracta
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 year2014
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

Workshop

WorkshopInternational Workshop on Computing with Terms and Graphs
Number8
CountryAustria
CityVienna
Period13/07/201413/07/2014

See relations at Aarhus University Citationformats

Download statistics

No data available

ID: 84452680