Re: The "Minsky bottleneck" ...and a solution? (Fritz Lehmann)
Date: Tue, 19 Jul 94 22:09:48 CDT
From: (Fritz Lehmann)
Message-id: <>
Subject: Re: The "Minsky bottleneck" ...and a solution?
References: <30ci0m$> <30d3rf$> <30g0h5$> <30hira$>
Distribution:  world
Organization: Center for Optimization and Semantic Control, Washington University
Precedence: bulk

In article <30hira$>, Jorn Barger <jorn@MCS.COM> wrote:
>In article <30g0h5$>,
>Fritz Lehmann <> wrote:
>>     Sorting relations by the sorts of their relata (fillers)
>>is _not_ enough.  There are hierarchies of relations,
>>ordered by subsumption, even on domains of uniform
>>sort (type).  Algebraically these are represented by
>>Boolean inclusion within locally finite cylindric set
>Gulp!  ;^/
>I'd *like* to understand this, but I don't have the cited texts...
>Can you give an example?
     Among transitive relations are various kinds of
mereological (part-whole) relations.  So being a 
physical sub-assembly and being within the the convex hull
are sub-relations of PART-OF, as is the incomparable
mass-mereology PART-OF, and these are all under the general
notion of PART-RELATION, which is in turn under the
TRANSITIVE-RELATION ("under" in the poset of relations).
The latter of course includes all sorts of other relations
both mathematical and empirically determined.

     Similarly various kinds of "oppositenesses" occur in
a hierarchy of such relations.

     If you consider "selling" as a relationship among the
seller, buyer, merchandise, and money (not that I necessarily
recommend conceptualizing it this way), then "auctioning" is
a subtype of the "selling" relation.  "Sealed bid" is a further
subtype, etc.

     In "Inferential Semantics", Parker-Rhodes, Harvester/Humanities
Press, Hassox, Sussex/Atlantic Highlands, NJ, 1978, there is a 
lattice of 25 "case relations" like AGENT, ROUTE, DONOR etc.

     Relations can be classified into hierarchies according
to their second-order qualities, like those in Huhns & Stephens'
work on the "transfers-through" relations in CYC.  See Proc.
IJCAI 1989.

     Martha Evens edited an excellent book on such classifications
of relations:  "Relational Models of the Lexicon", Cambridge Univ. 
Press, 1988.

     The foregoing are real-world "ontological" relational
hierarchies.  The formal treatment of relational subsumption
is pretty simple.   Suppose an n-adic relation to be, extensionally,
a subset of the set of all possible n-tuples 
in a universe of known-to-be-distinct individuals.  This can be
thought of as an n-dimensional product space of cells which take
the value 1 or 0.  If there are M individuals in the
universe, the size of the space is M^n.  If the relation
holds for certain individuals, say a triad relating a,b and c,
the the cell addressed (a,b,c) is a 1, otherwise a 0.
Subsumption of relation R1 by R2 then just means that every cell
which is a 1 in relation R1 is also a 1 in relation R2.
I.e. the 1's in R1 are a subset of those in R2.  This was
first studied by Charles S. Peirce in the 1860's and later developed
"algebraically" by Schroeder, Tarski and others.  A "relational
algebra" is by Tarski's unfortunate convention confined
to the case of dyadic relations (between two arguments).
For higher-valence relations they use the phrases
"cylindric algebras" and "polyadic algebras" depending
on which other features are present.  Through Codd, this
kind of theory became the theoretical foundation for
relational databases.

     The above simple notion is complicated in the case
of "omniscient" systems in which distinct individuals
can be perfectly symmetric and hence indistinguishable-
in-principle; see "The Theory of Indistinguishables",
A. F. Parker-Rhodes, Reidel, Dordecht, 1981.

     The standard text for the "algebraic" (equational)
approach of Tarski's school is "Cylindric Algebras" by
Henkin, Monk & Tarski, North-Holland, vI and vII, 1971
and 1985.  This addresses a lot of issues which I doubt
would concern you; a better and easier start in this
subject is "Relations and Graphs" by Schmidt & Stroehlein,
Springer, 1993.  The spaces of 1's and 0's are "Boolean
Matrices" and one neat thing is that matrix multiplication
= relative product (composition) of relations = joining
of two relational graphs by a line.  This yields a complete
"graph theory of descriptions" as in Peirce's Existential
Graphs or in various semantic network formalisms.

     If there is an _intensional_ theory of subsumption
of composite relational structures, I don't know of it.
That's something I'm working on, and I'd like to hear
from anyone who has worked on it.

                          Yours truly,   Fritz Lehmann
GRANDAI Software, 4282 Sandburg Way, Irvine, CA 92715, U.S.A.
Tel:(714)-733-0566  Fax:(714)-733-0506