Needed Computations Shortcutting Needed Steps

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object , Other literature type 26 May 2015Embargo end date: 01 May 2015 Denmark, United States English Publisher:Open Publishing AssociationJournal:Electronic Proceedings in Theoretical Computer Science, volume 183, pages 18-32 (eissn: 2075-2180,

Copyright policy )Funded by:NSF | SHF: Small: A principled ...

Authors: Antoy, Sergio; Johannsen, Jacob; Libby, Steven;

doi: 10.4204/eptcs.183.2 , 10.48550/arxiv.1505.07162

arXiv: 1505.07162

Needed Computations Shortcutting Needed Steps

- Summary
- Subjects
- Metrics

Abstract

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.

In Proceedings TERMGRAPH 2014, arXiv:1505.06818

Countries

Denmark, United States

Related Organizations

Keywords

FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Computational Complexity, Computer Science - Programming Languages, Logic in Computer Science, Computer Sciences, D.3.4, D.3.3;D.3.4;F.4.2;G.2.2, D.3.3, QA75.5-76.95, G.2.2, Logic in Computer Science (cs.LO), Electronic computers. Computer science, QA1-939, F.4.2, Computer Engineering, Mathematics, Programming Languages (cs.PL)

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	1
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average