Higher-Order KIF & Conceptual Graphs

fritz@rodin.wustl.edu (Fritz Lehmann)
Date: Sat, 13 Nov 93 08:23:22 CST
From: fritz@rodin.wustl.edu (Fritz Lehmann)
Message-id: <9311131423.AA14007@rodin.wustl.edu>
To: boley@dfki.uni-kl.de, cg@cs.umn.edu, interlingua@ISI.EDU
Subject: Higher-Order KIF & Conceptual Graphs

	My examples of candidates for higher-order logic included:

|46. Formal semantic definition of the classifying properties of
|complete partial and linear orders, lattices, and Boolean
|47. Formal semantic definition of the classifying properties of
|Scott-type domains.  [incl. in 46]
(The parenthetical remark means "including those in 46" which refers
to "topped" Scott-type domains under CPOs.)

	This brings up a serious practical concern.  KIF is explicitly
descriptive and not procedural.  (Conceptual Graphs' "actors" are
beyond KIF's purview.)  Many people (especially computer scientists
in Britain) propose declarative semantics for procedures and
programs.  There are over a dozen kinds of declarative semantics for
procedures, like Denotational Semantics, Vienna Semantics, Dynamic
Logic Semantics, Intensional Program Semantics, Various Algebraic
and Categorial Semantics, etc.  Scott-type domains are the basis for
the most popular, Denotational Semantics.  Since classifying Scott-
type structures requires strongly-higher-order definable predicates,
it seems that, by using only the First-Order pseudo-higher-order
kludge, KIF and declarative Conceptual Graphs are thereby excluding
the possibility of ever incorporating denotational semantics for

	Right now Alex Bejan and Michael Wermeliger are trying to
translate the PDES/STEP industrial language EXPRESS into Conceptual
Graphs; Jeffrey van Baalen is trying to translate EXPRESS into KIF. 
EXPRESS includes attached Pascal-like procedures with Turing-machine
capability, which requires some method like those just mentioned to
determine formal semantics (for purposes like tests of subsumption,
distinctness, equivalence, etc.).  Evidently, First-Order-ism will
defeat any attempt at a full translation of EXPRESS.

	Let's add a few examples to my list of candidates for requiring
higher-order logic:

[50]. [PAT HAYES' EXAMPLE]  Second-, third- (and fourth-?) order
constructs in Montague Grammars

51. The PDES/STEP EXPRESS industrial language including its
procedural attachment features.

52. Extended temporal logics, e.g that of Wolper, or Kozen's mu-

53. Propositional Dynamic Logics of Pratt and Kozen, Fischer &
Ladner.  Includes higher-order axioms.

54. The concept of connectivity of finite graphs.

55. The concept of planarity of finite graphs.

	To justify 54 and 55 I quote: "Originally, Ehrenfeucht-Fraisse
games were used to prove that certain concepts are not definable by
first order formulas even if restricted to finite structures.  Among
such concepts we find connectivity and planarity of graphs." J. A.
Makowsky, Model Theory and Computer Science, in v. I, Handbook of
Logic in Computer Science, S. Abramsky et al., Ed.s, Oxford U.
Press, 1992, p. 779.  If KIF and CGs really can't even define finite
connectivity, then I forsee trouble ahead.  I'm reminded of what the
same limitation of single-layer perceptrons did for neural network
research in the 1970's after Minsky & Papert's expose'.

	Also, I included in my list, without explanation:
|[49]. [MARK GRAVES' EXAMPLE] Inter-relation relations in genome
To clarify this I'll attach his note on this below.

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

From: Mark Graves <mgraves@cmb.bcm.tmc.edu>
Message-Id: <9311051610.AA12110@EAGLE.CELLB.BCM.TMC.EDU>
Subject: Re: Higher-order KIF & Conceptual Graphs
Date: Fri, 5 Nov 93 10:10:44 CST
Reply-To: mgraves@bcm.tmc.edu
Organization: Dept of Cell Biology, Baylor College of Medicine
Phone: (713)798-8271
X-Fax-Number: (713)798-3759
X-Phone: (713)798-8271


> [Fritz:]. . . (If anybody out
> there is sympathetic, please email to these lists a few
> more examples of higher-order or mixed-order statements.
> If unsympathetic, send counterexamples showing how my
> prior examples would appear in FO KIF or CGs.)

One example of relations between relations occurs in genome mapping.
Basically, it is difficult to discover an exact order for a
collection genes.  Thus, there are many different orders coming from
different sources and each estimated order has some (possibly
statistical) evidence for that order.  There then needs to be a
relationship (partial order) between the maps created by those
orders.  It is difficult to collapse this relation between relations
because of other constraints imposed on the mapping process.

If you want a reference, I can send you a paper on it: ``Integrating
Order and Distance Relationships from Heterogeneous Maps'', {\it
Proceedings of the First International Conference on Intelligent
Systems for Molecular Biology}, AAAI/MIT Press. Washington, DC,
July, 1993.

In general, I am very interested in modeling higher-order relations. 
I recently finished my dissertation under Bill Rounds at the
University of Michigan and part of my dissertation work contained a
way of looking at higher-order feature structures as a "higher-
order" graph logic.  I am now trying to apply some of that work to
developing a data model useful for genome databases.

Mark Graves
Baylor College of Medicine
Department of Cell Biology
One Baylor Plaza
Houston, TX  77030
email: mgraves@bcm.tmc.edu