Re: The IDS, the EDS and the DBMS

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Wed, 15 Sep 2004 16:06:08 GMT
Message-Id: <pan.2004.09.15.16.09.04.217597@REMOVETHIS.pandora.be>

On Tue, 14 Sep 2004 17:17:27 -0700, Mikito Harakiri wrote:

> "Jan Hidders" <jan.hidders_at_REMOVETHIS.pandora.be> wrote in message
> news:pan.2004.09.14.21.10.13.654821_at_REMOVETHIS.pandora.be...

>> On Tue, 14 Sep 2004 13:29:11 -0700, Mikito Harakiri wrote:
>> > The complexity of finite object can't be specified in absolute terms.
>>
>> Quite interestingly if you consider the operations over unnormalized
>> formulas (so no normalization at all and x + y is straightforwardly
>> represented as "(" x "+" y ")") then for both operations you also have an
>> upperbound of O(|x|+|y|).

>
> This is because that kind of symbolic representation is base-1 system:
>
> 5=1+1+1+1+1
>

>> The question about the complexity of normalization is also interesting.
>> From Tarksi we know that the reals are axiomatisable

>
> Finitely axiomatisable or not?

Yes, the first order theory of reals is finitely axiomatisable and in fact decidable. Ten points if you know why this not contradicts Goedel's incompleteness theorems. ;-)

• Jan Hidders

Received on Wed Sep 15 2004 - 11:06:08 CDT