Re: Propositions

• 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