research icon indicating copy to clipboard operation
research copied to clipboard

"Superoptimal" reduction strategies

Open cwgoes opened this issue 5 years ago • 0 comments

Namely, those with the possibly of asymmetrically-better performance than Levy's optimal reduction.

As far as I can tell, the only candidates here are forms of memoization which attempt to detect syntactically identical structures during the reduction process which can then be linked and evaluated only once.

Hash consing may have the most prior research.

Space-time tradeoff is the main concern here, I think.

cwgoes avatar May 25 '19 21:05 cwgoes