**Mail folder:**SRKB Mail**Next message:**Paul van der Vet: "Call for Papers KB&KS'95"**Previous message:**Fritz Lehmann: "Re: The "Minsky bottleneck" ...and a solution?"**Maybe in reply to:**Fritz Lehmann: "Re: The "Minsky bottleneck" ...and a solution?"**Reply:**Fritz Lehmann: "Re: The "Minsky bottleneck" ...and a solution?"

Date: Tue, 19 Jul 94 22:09:48 CDT From: fritz@rodin.wustl.edu (Fritz Lehmann) Message-id: <9407200309.AA06354@rodin.wustl.edu> Newsgroups: comp.ai,sci.logic Subject: Re: The "Minsky bottleneck" ...and a solution? References: <30ci0m$6hl@Mercury.mcs.com> <30d3rf$bh@mercury.mcs.com> <30g0h5$g18@bigfoot.wustl.edu> <30hira$nid@mercury.mcs.com> Distribution: world Organization: Center for Optimization and Semantic Control, Washington University Apparently-To: pratt@cs.stanford.edu Apparently-To: renate.schmidt@mpi-sb.mpg.de Apparently-To: cbrink@ucthpx.uct.ac.za Apparently-To: srkb@cs.umbc.edu Apparently-To: interlingua@isi.edu Apparently-To: cg@cs.umn.edu Sender: owner-srkb@cs.umbc.edu Precedence: bulk

[cc:cg@cs.umn.edu,interlingua@isi.edu,srkb@cs.umbc.edu, cbrink@ucthpx.uct.ac.za,renate.schmidt@mpi-sb.mpg.de,pratt@cs.stanford.edu] In article <30hira$nid@mercury.mcs.com>, Jorn Barger <jorn@MCS.COM> wrote: >In article <30g0h5$g18@bigfoot.wustl.edu>, >Fritz Lehmann <fritz@rodin.wustl.edu> 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 >>algebras. > >Gulp! ;^/ > >I'd *like* to understand this, but I don't have the cited texts... > >Can you give an example? > >j > 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 fritz@rodin.wustl.edu =============================================================