Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site ames.UUCP
Path: utzoo!watmath!clyde!cbosgd!ihnp4!pesnta!hplabs!ames!jaw
From: jaw@ames.UUCP (James A. Woods)
Newsgroups: net.misc
Subject: Re: Small World Redux (and reflexive transitive closure)
Message-ID: <879@ames.UUCP>
Date: Mon, 18-Mar-85 19:43:46 EST
Article-I.D.: ames.879
Posted: Mon Mar 18 19:43:46 1985
Date-Received: Thu, 21-Mar-85 02:00:42 EST
References: <542@ahutb.UUCP> <1308@ut-sally.UUCP>
Organization: NASA-Ames Research Center, Mtn. View, CA
Lines: 34

# Resist specialization.

     The connection concept is an common lllustration of the
"reflexive transitive closure" graph/matrix operation arising
in the study of LALR parsing lookahead sets.  Translation:
the Unix 'yacc' program probably computed this type of closure
when building the C compiler.  I assume that a variant
of the technique is used by 'pathalias' to construct minimal
mail paths, only with transition probablities assigned to each
graph arc.  It's best to consult a standard text on formal
languages such as Aho/Hopcroft/Ullman for definitions.

     It has been surmised that the closure of the world is around seven,
if handshakes are taken as the metric.  I'd guess that closure of this
net is less than that, as all roads seemingly lead to 'ihnp4' --
ask down!honey.

     One can imagine extensions into the "fuzzy" domain to
categorize more informal relation types.  Somehow I doubt that the
Bureau of the Census keeps this kind of data, though it would
be a boon to conspiracy theorists.

     Other "applications":  If you've ever wondered about the origins
of your junk mail, you can compute a rough "closure" by salting
surname spelling variants into magazine subscriptions/mailing lists.
And, if you want to optimize your success with chain mail or pyramid
schemes, pick victims who have low closure (i.e. many connections).
This is just common sense, really.

     Oh, and don't forget the immortal "How to be your own grandfather"
puzzle, popularized by Mark Twain, wherein the establishment of this
non-intuitive kinship shown to be physically possible.

     -- James A. Woods   {ihnp4,hplabs}!ames!jaw