# Re: Ex-Con logic

attardi@ICSI.Berkeley.EDU (Giuseppe Attardi)
From: attardi@ICSI.Berkeley.EDU (Giuseppe Attardi)
Date: Mon, 21 Feb 1994 17:33:18 -0800
Message-id: <199402220133.RAA14756@icsib32.ICSI.Berkeley.EDU>
To: schubert@cs.rochester.edu
Cc: boley@dfki.uni-kl.de, cg@cs.umn.edu, fritz@rodin.wustl.edu,
interlingua@ISI.EDU, simi@ICSI.Berkeley.EDU
In-reply-to: <199402212322.SAA07435@cherry.cs.rochester.edu> (schubert@cs.rochester.edu)
Subject: Re: Ex-Con logic

I hope the latest remarks by Schubert settle this issue.
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?
So notation can only matter in problems of polynomial complexity: and
this is what algorithm designers consider when they select appropriate data
structures and build parsers to perform suitable input transformations.
And to answer Sowa's reminder:
The need for
a language-independent definition of "proposition" was the original
motivation for this discussion.
one can suggest one such definition: McCarthy's "abstract syntax". Any
semantic equivalence relation about propositions can be defined in
terms of it.
-- Beppe