**Mail folder:**Interlingua Mail**Next message:**schubert@cs.rochester.edu: "wffs vs graphs"**Previous message:**macgregor@ISI.EDU: "Re: Propositions"**In-reply-to:**macgregor@ISI.EDU: "Re: Propositions"**Reply:**Michael R. Genesereth: "propositions"

From: Gerard Ellis <ged@cs.rmit.oz.au> Message-id: <199402250150.MAA15710@goanna.cs.rmit.oz.au> Subject: Re: Propositions To: cg@cs.umn.edu Date: Fri, 25 Feb 1994 12:50:03 +1100 (EST) Cc: interlingua@ISI.EDU In-reply-to: <199402250044.AA25850@quark.isi.edu> from "macgregor@ISI.EDU" at Feb 24, 94 04:45:14 pm X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 2580

Bob MacGregor writes: > From Len, commenting on Sowa's comments. > >Well, exactly -- the problem then becomes graph-theoretic, and I'm > >not convinced it'll make the proposition-equivalence problem simple. > >It's the "easily computable" part that I don't find at all obvious. > Unless I'm missing something, computing equivalence on Sowa's graphs > is easily reducible to the general problem of (directed) graph isomorphism. > I don't follow concrete complexity results any more, but when I did, no one > had yet found a polynomial time algorithm (and a lot of people had worked > pretty hard trying to find one). Perhaps John means that > its easy to compute graph equivalence in the average case (I would > agree with that). I agree with this, but we should point out what makes conceptual graphs attractive in a computational sense. For example, the graph of ``John believes Mary is smart.'' [PERSON: John]->(BELIEVES)->[PROPOSITION: [PERSON:Mary]->(CHRC)->[SMART]] This may appear to be a graph of 5 nodes or more, but is really a graph of 3 nodes. The label of one node just happens to be a graph as well. The graph of ``A person believes some proposition'' is a generalization of 3 nodes. [PERSON]->(BELIEVES)->[PROPOSITION] This is important because the exponent of the exponential complexity of graph matching is the number of nodes. Contexts have reduced it from 2^5 to 2^3. Of course complexity of matching the node labels is not constant, but neither is it related to the complexity of the outer context. This ability to hide information in contexts is not unique to conceptual graphs, but it is a very useful aspect, just as using types or sorts has made problems such as schubert's steamroller tractable, so does the addition of contexts reduce the complexity of much larger problems. The major computation tool of conceptual graphs/terminological or description logics is the generalization hierarchy. The generalization hierarchy is a contents addressable memory which organizes graphs/propositions by generalization and querying becomes classification of formulas. This an other techniques for managing conceptual graphs are discussed in @phdthesis{Ellis94thesis, author = {Gerard Ellis}, title = {Managing Complex Objects}, school = {The University of Queensland}, note = {in preparation}, year = {1994}} Regards, Gerard. -- Gerard Ellis ged@cs.rmit.edu.au ph:61-3-660-2544 FAX:61-3-662-1617 Rm:12.10.09 Computer Science Dept, Royal Melbourne Institute of Technology GPO Box 2476V, Melbourne, Victoria, 3001, AUSTRALIA