Re: Ex-Con logic

phayes@cs.uiuc.edu
Message-id: <199402221928.AA25435@dante.cs.uiuc.edu>
X-Sender: phayes@dante.cs.uiuc.edu
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Date: Tue, 22 Feb 1994 13:35:14 +0000
To: attardi@ICSI.Berkeley.EDU (Giuseppe Attardi), schubert@cs.rochester.edu
From: phayes@cs.uiuc.edu
Subject: Re:  Ex-Con logic
Cc: boley@dfki.uni-kl.de, cg@cs.umn.edu, fritz@rodin.wustl.edu,
        interlingua@ISI.EDU, simi@ICSI.Berkeley.EDU

At  5:33 PM 2/21/94 -0800, Giuseppe Attardi wrote:
>I hope the latest remarks by Schubert settle this issue.

Settle? Not a chance...:-)

>It is fairly clear to me that a simple change of notation will not
>make any problem disappear.
>If a problem is exponential, a change in notation, which is a polynomial
>transformation, will not change its nature, right?

A and B are trying to do arithmentic. If A can only use +, but B can also
use * and !, then A has an exponential problem which B has solved by a
change in notation.

....
>one can suggest one such definition: McCarthy's "abstract syntax". Any
>semantic equivalence relation about propositions can be defined in
>terms of it.

But abstract syntax, as I understand it (and I would love to be corrected) 
can only abstract away from particular ways of displaying the local
syntactic structure of expressions: the differences between 'a+b' and
'+(a,b)' and '*PLUS A B' and so forth. It still cannot account 'abstractly'
for the relationship between a quantifier and the locations it binds, since
this relationship simply does not fit into the recursive syntax. The only
way to get it in is by introducing tokens which somehow indicate lexically
the required relationship between locations in the parse tree, and these
are bound variables. Abstract syntax describes (rather than displays)
recursive syntax, but it is still wedded to the recursive nature of its
specification.

Pat Hayes


----------------------------------------------------------------------------
Beckman Institute                                    (217)244 1616 office
405 North Mathews Avenue        	   (217)328 3947 or (415)855 9043 home
Urbana, IL. 61801                                    (217)244 8371 fax  	  

hayes@cs.stanford.edu  or Phayes@cs.uiuc.edu