Re: The "Minsky bottleneck" ...and a solution? (Fritz Lehmann)
Date: Fri, 22 Jul 94 05:26:03 CDT
From: (Fritz Lehmann)
Message-id: <>
Subject: Re: The "Minsky bottleneck" ...and a solution?
References: <30g0h5$> <30hira$> <30i4ho$> <>
Organization: Center for Optimization and Semantic Control, Washington University
Precedence: bulk

In article <>,
Michael Zeleny <> wrote:
>In article <30i4ho$> 
> (Fritz Lehmann) writes:
>[... material omitted...]
>>     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.
>So far, so good.
>>     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.
>I have been meaning to look this up; thanks for reminding me.  Is
>the Russian Formalist narratology really being reinvented by the
>artificial intelligentsia?

     Aha -- is this another vast untapped Russian school of thought
for A.I. (like that of Yu. Shreider in conceptual lattice theory)?
Please explain "Russian Formalist narratology", whether it's any good,
and where we can find material on it (in English, if available).
If "Russian Formalist narratology" has carefully reasoned taxonomies
of narrative elements, it might very well be a valuable resource
for common-sense "ontology" or concept-system building.  So, tell us.

>>     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.
>How is this related to cognate work in descriptive linguistics?

     I don't know about the "descriptive", but this book is
closely tied to what is called _cognitive_ linguistics.  
(Descriptive linguistics is a phrase sometimes used for
that linguistics which militantly refuses to be cognitively
based, or to acknowledge that language has much to do with

>>     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.
>A nice summary.  You might also have cited Venn.  All of the original
>books and papers are available in Chelsea, Birkhauser, and Hackett
>reprints.  Save your pennies and hold your breath for the 30 volumes
>of Peirce coming out of the Indiana University Press.

     No need to wait.   Volumes 2, 4 and 5, already published,
contain the founding papers on relational algebra.  We will
have to wait for the volumes in which he discloses the graphic
notation for relations (and predicate calculus which he and his
student O. H. Mitchell invented independent of Frege), namely the 
Existential Graphs, which he considered superior and "the logic
of the future".  Both subjects already appear in "The Collected
Papers of Charles S. Peirce", Harvard U. Press (Belknap), also
now available on a CD-ROM.  A typed version of Existential Graphs
is now used in A.I. in the form of John Sowa's Conceptual Graphs.
>>     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.

>I would appreciate pointers to reviews of and responses to Parker-Rhodes.

     So would I.  In Physics, Linguistics, A.I. or Mycology?  He was
active in all four.  The recent response in A.I. was almost nil prior
to my "Semantic Networks" collection, as far as I know.  Yorick
Wilks and Karen Sparck Jones knew him in the old days when he
worked closely with Margaret Masterman at the Cambridge Language
Research Unit (where semantic networks were invented in the late
1950's), but they rarely if ever cite him.  In Physics (to my
utter surprise) I found that there are two societies founded
on his ideas for a combinatorial basis for the physical world.
(ANPA and ANPA-West, meeting at Cambridge and Stanford, resp.)
The subtitle to the above book is "A Search for Explanatory
Principles below the Level of Physics."  I suspect that this
book falls under the heading of "more admired than understood".
Parker-Rhodes was a _very_ independent thinker.  I think you saw
my earlier posting in the newsgroup sci.skeptic about his
unpublished posthumous work "The Inevitable Universe", in which
all kinds of specific physical constants are derived from an
exceedingly sparse ontological axiom set.

>>     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.
>You might have mentioned Halmos' work in algebraic logic, collected in
>the eponymous Chelsea volume.  Also, I recall that Monk's Handbook of
>Boolean Algebras contains some relevant material.  Other useful bits
>may be found in Birkhoff's books on lattice theory, and the first
>volume of Bourbaki.

     Yes -- polyadic algebras are due to Halmos.

>>     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.
>What you want to do, is study Church's Logic of Sense and Denotation,
>as reformulated in Nous in 1973--4, and 1994.  Your primary focus
>should be the computationally closed individuating principle of the
>Alternative (1), as treated in the most recent publication.  The next
>step is to take a look at the relational reformulation of Church's
>extensional theory of types.  Unfortunately, I do not have a reference
>to the paper that describes it, but as far as I can recall, it was
>published in the JPL in the mid-Seventies.  Church's analysis of
>intensions easily generalizes to all flavors of type theory, and
>affords a theoretical framework for promulgating your favorite
>subsumption theory to arbitrarily finely discriminated levels of
>intensional relations.

     Thanks -- this looks promising.

>In turn, I would like to hear more about this sort of research in
>applications of intensional logic to theoretical computer science.

     Everybody pretty much agrees on what extensions and extensional
logic are.  There are umpteen different notions of what "intensional"
and "intensional logic" mean (which in no way diminishes their
importance).  All of A.I. able to distinguish an arbitrary set from a
set of individuals having something in common necessarily has intension.
You could get several different understandings of your question.


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