Higher-Order KIF + Conceptual graphs

fritz@rodin.wustl.edu (Fritz Lehmann)
Reply-To: cg@cs.umn.edu
Date: Mon, 15 Nov 93 07:37:46 CST
From: fritz@rodin.wustl.edu (Fritz Lehmann)
Message-id: <9311151337.AA16216@rodin.wustl.edu>
To: phayes@cs.uiuc.edu
Subject: Higher-Order KIF + Conceptual graphs
Cc: boley@dfki.uni-kl.de, cg@cs.umn.edu, interlingua@isi.edu

     Pat Hayes said:
>Oh then we *arent* arguing past one another, Fritz. Suppose we were to
>agree on the utility of a higher-order syntax of some kind, for pragmatic
>reasons of expressiveness in Krep.

     I do agree to that.

>However, I will insist that we have no warranty
>to claim that these quantifiers can be taken as ranging over >*all*
>(uncountably many) higher-order functions. You say they can: but since you
>abandon completeness, you are in exactly the position of my student who
>simply claims that "is-very-big" denotes what he intends it to denote.
>Suppose we set up stalls opposite one another at a Krep trade fair, you
>selling strong higher-order logic and me selling weak higher-order (which
>we all know is really first-order) logic. Apart from the semantic theories
>we put in the manuals, we will be selling the same logics.

     "Same logics?"  Well maybe this might be true, except that some of our
55 examples do need the real thing and I don't yet know that those examples
are all just esoteric irrelevancies.  For example, no. 54, connectedness of
finite structures, seems like a pretty mundane and useful concept, not a
piece of transfinite exotica.  Practical notions of relevance are based on
connectedness of a semantic network.  Electric circuit theory uses
connectedness.  Yet defining finite "connectedness" is said by Makowsky to
require higher-order logic according to Ehrenfeucht & Fraisse's proofs. 
And, are you convinced that No. 26, your example of Beta-reduction of
lambda-sentences, has no real uses?

>So I dont see
>how you can justify your claims to this useful expressiveness that my weak
>logic doesnt have. People could buy mine and tell your story about it,
>after all.

     Pat, I see two questions:
1. Is there any PRACTICAL difference, in the real-world
expressiveness and usefulness of a knowledge interchange language
(closed under sets and unions of direct products), between basing
it on real, strong, higher-order semantics, and basing it on weak
(First-Order) pseudo-higher-order semantics?

2. If the answer to 1 is definitely "no", is there any other
PRACTICAL reason to favor one over the other?  If completeness
and compactness (of the pseudo method) are at all practically
desirable for knowledge interchange, somebody should demonstrate
why.  Otherwise we might as well use the real thing rather than
an elaborate and inelegant imitation, all other things (question
1) being equal.

     Although I've brought up examples that might need true
higher-order concepts, I'm not at all dogmatic or certain about
this.  I emphasized to Mike Genesereth and Thomas Uribe that any
practical equivalent would do as well.  At present, I simply do
not know the answer to question 1.  Question 2 might just reduce
to a matter of aesthetic taste.

     I'm not going to have a K.Rep "booth" (I'm for CGs & KIF in
any case), but if I did have a booth, and my language could
define anything yours can, plus familiar predicates like NATURAL
NUMBER or CONNECTED (for finite structures) which yours could
not, I'm not so sure which one people would buy.

                         Yours truly, Fritz Lehmann
4282 Sandburg, Irvine, CA 92715 USA    714-733-0566