[OT] Just curious: What's this algorithm's name?

[Nick Sabalausky]

"H. S. Teoh" <hsteoh at quickfur.ath.cx> wrote in message 
news:mailman.1351.1333549896.4860.digitalmars-d at puremagic.com...
> On Wed, Apr 04, 2012 at 01:33:21AM -0400, Nick Sabalausky wrote:
> [...]
>> Suppose you have a directed graph, which may have cycles, and you want
>> to compute something for each node. But the final result for each node
>> is dependent on the final results for each of the nodes it points to.
>> (It may sound like this would just cause an endless "feedback loop" ie
>> infinite recursion whenever there's a cycle, but there are
>> applications of this where that isn't a problem. Ie, in cases where
>> the computation stops recursing when it gets back to itself.)
>
> Sounds like the word you want is "closure".
>

Now that you mention it, that *does* seem to make sense: (Warning: Little 
bit of LALR internals here) The LALR theory materials I had read didn't 
refer to what I just desribed (ie, basically the lookahead generation) as 
"closure". But before that, when actually generating the state graph itself, 
it did use the term "closure" for going from what it called the "kernel" 
items in a state to the entire state with *all* applicable items included. 
The algorithm looked a little different, but now that I think about it, 
those "kernel" items *are* essentially the "spontaneously generated" 
elements (and computing them involves looking at another graph - the AST of 
the grammar's BNF-like description). And then computing what it called the 
"closure" of the state is essentially the same as the "step 2" I described, 
traversing the graph of the BNF over and over to find new elements until 
there's no new elements found.

It would indeed appear that the term "closure" the books used for state 
graph generation is also applicable for the lookahead generation algorithm I 
described in the OP.

I think another part of what made me not realize to call it "closure" is 
that somehow I had the impression of "closure" being a much more general, 
even nebulous term. For example, I knew I'd also heard it used in the 
context of database theory. But, looking that up now, that *is* the same 
damn algorithm, too.

So I guess a /facepalm is in order here ;)

Thanks!