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>
        interlingua@ISI.EDU, simi@ICSI.Berkeley.EDU
In-reply-to: <> (
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