wffs vs graphs

• Mail folder: Interlingua Mail
• Next message: John McCarthy: "wffs vs graphs"
• Previous message: Gerard Ellis: "Re: Propositions"
• Reply: John McCarthy: "wffs vs graphs"
• Reply: Don Dwiggins: "Re: wffs vs graphs"

Date: Fri, 25 Feb 1994 13:46:14 -0500
From: schubert@cs.rochester.edu
Message-id: <199402251846.NAA15811@cherry.cs.rochester.edu>
To: boley@dfki.uni-kl.de, cg@cs.umn.edu, fritz@rodin.wustl.edu,
        interlingua@ISI.EDU, phayes@cs.uiuc.edu, schubert@cs.rochester.edu
Subject: wffs vs graphs

> But look. Suppose I were to insist that since graphs must be printed or
> displayed, any perceptible 'token' graph will have its nodes and lines
> displayed in some position on the screen; therefore, the problem of graph
> matching is the problem of matching bitmapped pictures of graphs. This
> would clearly be a perverse position ...

Well, keystrokes are (at least at present) more tractable tokens for
on-line processing than bitmaps. But we *do* have to start with tokens.

You mention the possibility of wff-matching aided by a kind of graphical
representation of variable bindings, and remark,

> quantifier binding structure does not naturally 'fit' into the usual 
> recursive may of parsing syntax, and that bound variables are only 
> a device, and perhaps a rather artificial one, for making it fit

One way of making it fit is by skolemization, and I suppose that may be
why network theorists (inlcuding me) have tended to use some sort of 
skolem-like form of implicit quantification. But as far as I can tell,
this doesn't help with the matching problem. As you say,

> It will be necessary to consider permutations of &, of course, and that
> seems to me to be the real difficulty. Unfortunately it does not seem that
> anything is going to be able to help with the worst case ...

I've talked with a colleague about this, and he says

1. This does look like DAG-isomorphism, which is equivalent to graph
   isomorphism in general, for which it is still not known whether
   it's polynomial, just as Bob McGregor surmised (except for bounded 
   degree graphs, which we can't restrict ourselves to if we want 
   polyadic conjunction and disjunction)

2. A graphical representation of a formula could be exponentially
   more compact than a string representation, by avoiding subexpression
   repetition. 

The latter is an interesting point. But as I noted in my article in
John's book, one can augment standard logical syntax with subexpression
names, getting something even closer to network syntax. With these
names, the wff-syntax can completely avoid subexpression repetition,
and also allows cycles (e.g., Liar sentences, illustrated in the paper).
Feature logics, whose relevance to this discussion I previously
mentioned, also use names for shared functional expressions, avoiding
repetition. (Our input syntax for episodic logic in the EPILOG system
also allows subexpression naming.)

Len