**Mail folder:**Interlingua Mail**Next message:**Fritz Lehmann: "Recursive Peirce"**Previous message:**Fritz Lehmann: "Higher-Order KIF and Conceptual Graphs"**In-reply-to:**Fritz Lehmann: "Higher-order KIF & Conceptual Graphs"

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 |algebras. | |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 programs. 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- calculus. 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 |mapping. To clarify this I'll attach his note on this below. Yours truly, Fritz Lehmann fritz@rodin.wustl.edu 4282 Sandburg, Irvine, CA 92715 USA 714-733-0566 ====================================================== BEGIN INCLUDED NOTE FROM MARK GRAVES: 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 [OMITTED MATERIAL] > [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. Thanks, Mark Graves Baylor College of Medicine Department of Cell Biology One Baylor Plaza Houston, TX 77030 email: mgraves@bcm.tmc.edu ========================================================= END OF INCLUDED NOTE