**Mail folder:**SRKB Mail**Next message:**Gio Wiederhold: "Re: Responses"**Previous message:**sowa@watson.ibm.com: "Coalition of logic-based standards efforts"

Message-id: <9111161805.AA07133@venera.isi.edu> Date: Sat, 16 Nov 91 12:59:08 EST From: sowa@watson.ibm.com To: RATHMANN@eclipse.stanford.edu Cc: SRKB@isi.edu, INTERLINGUA@isi.edu Subject: Languages and metalanguages

Peter, Your comments and questions are very well taken, and I'm sure that a lot of other people have similar questions. Following are my comments on your comments: > I have a few questions left over from your presentation last Friday, > and the meeting at KSL last Tuesday. Since the overall goal is to make > the IRDS standards and the knowledge sharing effort languages as > compatible as is possible, I wanted to be sure I had a clear vision of > the IRDS proposal. First, I must emphasize that the ANSI proposal for the IRDS conceptual schema is still very much work in progress. The only thing that is down in writing is a 20-page working paper that will be presented to ISO. (I sent a copy of that paper without the diagrams to SRKB and INTERLINGUA mailing lists on October 18.) For conceptual graphs, the starting point for most implementations has been my 1984 book, but almost everybody who has worked with them deviates >From the book in one way or another. In recent papers, I have stayed fairly close to the book, but I have added some extensions and have clarified some points that were not clear in the book. So the term "conceptual graph" or the abbreviation CG is very much a moving target. KIF is also a moving target, and it should continue to move as more people start to work with it and add more requirements. Therefore, I will use NKIF for the "normative KIF" that we would like to make an ANSI and ISO standard at some point in the future, say 1995. I will use NCG for the "normative conceptual graphs" that we would like to define as semantically equivalent to NKIF. > Could you let me know if the following are correct statements? > 1) The second-order constructs of conceptual graphs, as used in IRDS, > can all be expressed, although less compactly, in first order logic. The general CG notation was designed as a semantic representation for natural language, and it therefore allows almost any kind of mixture of modal, intensional, and higher-order forms that occur in unrestricted natural language. NKIF and NCG are likely to be much more disciplined. In my talk on Friday, I said that I prefer to use first-order logic as much as possible. Therefore, I would like to treat second-order logic as a version of first-order logic whose domain of discourse is some other first-order system. As an illustration, following is a second-order conceptual graph that says that the relation mother-of is a one-to-many, irreflexive relation (this is in the linear notation for conceptual graphs, which uses brackets for the boxes and parentheses for the circles): [Relation: mother-of]- (ATTR)->[Irreflexive] (CHRC)->[Cardinality: <1,many>]. ATTR is the attribute relation and CHRC is the characteristic relation. Informally, you can say that ATTR is used with adjectives and CHRC with nouns, although I have a more formal characterization of the distinction. The formula operator phi translates this graph to the following formula in predicate calculus: (Ex)(relation(mother-of) & irreflexive(x) & cardinality(<1,many>) & attr(mother-of,x) & chrc(mother-of,<1,many>)). This formula says that there exists an instance of irreflexivity x, the relation mother-of has x as an attribute, and it has a characteristic cardinality <1,many>. Note that this formula looks like first-order logic. In fact, it is a formula in an easily decidable logic with only conjunction and existential quantifiers. What is odd is its domain of discourse, which includes constants like "mother-of" and "<1,many>" and quantification over weird things like instances of irreflexivity. In pure first-order CGs, we can say that mother-of is irreflexive by a rule of the following form: IF [Person: *x]->(Mother-of)->[Person: *y] THEN [*x]-(^=)-[*y]. This says that if person x is the mother of person y, then x is not equal to y. (The asterisk distinguishes variables from constants. In the pure graph form, you don't need any variables at all, and even in the linear form, the number of variables is usually less than in the corresponding formula in predicate calculus.) I define IF and THEN as macros for nested negative contexts, as in C. S. Peirce's logic. Therefore, this graph maps to the following formula: ^(Ex)(Ey)(person(x) & person(y) & mother-of(x,y) & ^( x/=y)). which is equivalent to (Ax)(Ay)((person(x) & person(y) & mother-of(x,y)) -> x/=y). Note that Peirce's conventions allow you to use existential quantifiers in the IF-clause instead of transforming them into universals in front of the formula. In most cases, this gives you a more natural English reading for the graphs. We still need some way to relate the second-order graphs to the first-order graphs. That can be done by an IF-THEN rule with the second-order graph in the antecedent and the first-order graph in the consequent: IF [Relation: *r]->(ATTR)->[Irreflexive] THEN [IF [*x]->(rho *r)->[Person: *y] THEN [*x]-(^=)-[*y]]. Note the Greek letter rho. It represents an operator that maps constants of type Relation in the second-order graphs into relations in the first-order graphs. I prefer to use lower-case for constants in second-order graphs and upper case for relations in first-order graphs. Therefore, you could define Mother-of = rho mother-of. The rule that relates the metalanguage to the target language belongs to a metametalanguage whose domain is the union of the domains of the target language and the metalanguage. It also includes the operators rho and tau for mapping individuals in the metalanguage to relations and types in the target language. Unrestricted use of rho and tau could lead to an extremely complex undecidable system. But if you restrict them to rules of this form, you get simple translation rules for deriving the first-order formulas from the second-order ones. > 2) The logic expressed in IRDS includes integers, +, *, and > exponentiation, so even though it is first order, it is not > semi-decidable. What makes Peano's axioms undecidable is the axiom of induction, which is not first order. You can have a restricted theory in which you introduce arithmetic operators and functions one at a time as you need them, but you allow induction only in the metalanguage, not the target language. Such a language could be decidable, but you would have to go to the metalanguage if you wanted to add any new functions and operators. > 3) KIF includes some higher-order constructs which can not be reduced > to f.o.l., to encode various closed-world assumptions, inheritance with > exceptions, etc. I assume these operations can not be directly > expressed in IRDS? This mismatch in expressiveness will complicate > interoperability between the two standards. We must include all these features in the IRDS. There are database systems in use today that have null values, defaults, and open-world assumptions with truth values {T, F, Unknown}. The IRDS must be able to describe them. I attended John McCarthy's talk at CSLI on Nov. 7, where he discussed contexts as first-class objects. I like that approach very much. I think that you can use it to axiomatize theories in which the truth values of the metalanguage are very different from the truth values of the target language. For example, you could have a metatheory with the truth values {T,F} whose domain of discourse includes a set {T',U',F'}, which happens to be the truth values of the target language. But you would not identify T=T' or F=F'. > If there is indeed a mismatch in expressiveness between IRDS and KIF, > then we could extend IRDS to include the extra constructs, but this > would mean sacrificing the good computational properties of IRDS in > order to include constructs which are extraneous to its main mission > -- defining dictionaries, constraints, etc. Alternately, we could > accept a partial mapping for the KIF --> IRDS translation, with the > usual idea that unexpressible constructs show up as structured > comments. Just making sure the mapping is clean on the appropriate > subset of KIF would be a great boon to both standards, I think. I think that we would like to have good computational properties in both the IRDS and KIF. But you may have to state rules for the kinds of things that allow a nice tractable system and those things that lead you into an intractable swamp. Since the goal of CGs is to represent anything that anyone might say in natural language, they must be able to represent all kinds of absurdities and paradoxes. But there should be criteria that warn you when you approach a danger zone. There are many decidable subsets of logic that can be determined by syntactic checks. When you go beyond those subsets, the system might allow you to say what you want, but give you a warning message: "You have just said something that might be lead to a paradox." The system wouldn't have to prove that your statement was indeed paradoxical; it could just say that violations of the rules for using rho and tau might lead you into trouble. If you are really looking for trouble, the system should warn you, but let you do what you want. John