Higher-Order KIF and Conceptual Graphs

fritz@rodin.wustl.edu (Fritz Lehmann)
Reply-To: cg@cs.umn.edu
Date: Thu, 11 Nov 93 08:19:17 CST
From: fritz@rodin.wustl.edu (Fritz Lehmann)
Message-id: <9311111419.AA10808@rodin.wustl.edu>
To: uribe@cs.stanford.edu
Subject: Higher-Order KIF and Conceptual Graphs
Cc: boley@dfki.uni-kl.de, cg@cs.umn.edu, interlingua@isi.edu,

Dear Thomas Uribe,                   uribe@cs.stanford.edu

	You wrote, on my suggesting a higher-order semantics
for KIF and Conceptual Graphs:

>Um, Chapter 8 of the KIF reference manual describes how functions
>and relations can be defined... Given these definitions, one can
>proceed to quantify over them, and thus define functions of
>relations over relations, and so on (i.e., the "individuals" over
>which the functions and relations range over are functions and
>relations themselves).

	As I said in my recent reply to Mike Genesereth:
        "Yes, one can _refer_ in KIF to countable sets, and
         sets of these sets, as reified objects.  (This includes
         relations if interpreted as sets of finite, "ordered"
         sequences of objects.)  It isn't clear to me how actual
         quantification on (the recursive closure of) these objects
         has adequately expressive semantics, though, if the
         interpretation is only First-Order."

	The problem is the quantification.  So-called "Weakly Higher-
Order" languages reify relations into individuals but do not have
true higher-order quantification over them.  "Strongly Higher-Order"
languages have true higher-order quantification over ALL relations
and this includes their recursive closure.  A First-Order mock-up is
not deemed to be quite the same thing.  Concepts equivalent under
one may be incomparable in the the other.  A First-Order model-
theoretic semantics for a weakly higher-order language is no higher-
order semantics at all -- it is still just First-Order.  My original
email inquiry in September suggested strongly higher-order
semantics, sacrificing formal completeness and compactness but
gaining useful expressiveness.

>> I think I've cited examples of about five or six. . .

>Have these examples been sent out to the Interlingua list?
>I don't recall seeing them...

	Yes they have. See my next email message.  It turns out that
the "about five or six" were closer to 50.

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