[FoRK] Re: Combinator Correction!
Dave Long <
dave.long at bluewin.ch
> on >
Sat Sep 16 03:41:10 PDT 2006
> Quadratic is still not "exponential".
Right, but (if the kragen-hacks post* is what we're discussing) when
one uses nodes to share subgraphs, that's performing graph reduction
instead of string reduction.
The original claim was exponential, in the absence of naming or
sharing. This is a more explicit statement; is it accurate?
names/lambda --n^x--> shared nodes/G-machine --x^n--> strings/SK
:: :: ::
More information about the FoRK