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

[H. S. Teoh]

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.


T

-- 
Prosperity breeds contempt, and poverty breeds consent. -- Suck.com