Published In
8th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2014); also EPTCS 183, 2015
Document Type
Article
Publication Date
2015
Subjects
Logic in Computer Science, Computational Complexity
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.
DOI
10.4204/EPTCS.183.2
Persistent Identifier
http://archives.pdx.edu/ds/psu/16623
Citation Details
Antoy, Sergio; Johannsen, Jacob; and Libby, Steven, "Needed Computations Shortcutting Needed Steps" (2015). Computer Science Faculty Publications and Presentations. 138.
http://archives.pdx.edu/ds/psu/16623
- Citations
- Citation Indexes: 1
- Usage
- Downloads: 90
- Abstract Views: 17
- Captures
- Readers: 2
- Mentions
- References: 1
Included in
