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

[Nick Sabalausky]

"H. S. Teoh" <hsteoh at quickfur.ath.cx> wrote in message 
news:mailman.1358.1333576694.4860.digitalmars-d at puremagic.com...
> On Wed, Apr 04, 2012 at 05:03:39PM -0400, Nick Sabalausky wrote:
>> "H. S. Teoh" <hsteoh at quickfur.ath.cx> wrote in message
>> news:mailman.1351.1333549896.4860.digitalmars-d at puremagic.com...
> [...]
>> > 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)
> [...]
>
> I'm familiar with LALR internals. :-)
>
>
> [...]
>> 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 ;)
> [...]
>
> Well, the term itself *is* quite general. Mathematically speaking, for
> something to be "closed" means that every combination of operations on a
> set results in something that is already in the set. It's closed in the
> sense that no operation will get you "outside the set". So what's a
> closure? Given a set that *isn't* closed (i.e., some operations may take
> you "outside the set", so to speak), the "closure" of the set is a
> larger set that *is* closed.
>
> OK, an example is in order. Take the set A={0,1,2} and the operation +.
> A is not closed, because although 0+1 and 0+2 are in A, 1+2 is not in A.
> To form a closure, then, we take the elements produced by + that aren't
> already in A, and add them to A. So for example, we add 3 to A, now 1+2
> is closed. But then 2+2 is not in the set. No problem, we just add that
> to the set too. But now the newly added elements 3 and 4 are themselves
> not closed under +, because 1+4 isn't in the set, for example. So we
> have to add *those* elements as well. (I hope you can see the parallel
> here with the algo in your OP -- you're trying to incrementally compute
> the closure.)
>
> Taken to its logical conclusion, we find eventually that in order for A
> to be closed under the operation +, we have to add *all* positive
> numbers to it. So the closure of A is actually the entire set of natural
> numbers.
>
> Now, this example isn't exactly the best one, because the closure is
> infinite, so an incremental algorithm to compute it would never
> terminate. However, not all closures are infinite. Closure under grammar
> rule applications, like in your OP, is finite. Basically you keep
> applying the rules until it doesn't yield anything more that you don't
> already have. Then you can stop, because you've found the closure.
>

Yea, that makes sense. I've been starting to think of it like: In both 
everyday english and in math/CS, "closure" is essentially "Everything's 
taken care of, no loose ends". Not a good technical definition, of course, 
but a way to help remember an internalize it.