Re: Ex-Con logicattardi@ICSI.Berkeley.EDU (Giuseppe Attardi)
From: attardi@ICSI.Berkeley.EDU (Giuseppe Attardi)
Date: Mon, 21 Feb 1994 17:33:18 -0800
Cc: email@example.com, firstname.lastname@example.org, email@example.com,
In-reply-to: <199402212322.SAA07435@cherry.cs.rochester.edu> (firstname.lastname@example.org)
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.