Re: Normalisation

From: Jan Hidders <>
Date: Tue, 12 Jul 2005 21:11:52 GMT
Message-ID: <smWAe.143397$>

Jon Heggland wrote:
> In article <OI5Ae.141460$>,
> says...

>>Come on, Jon. How much tape does the Turing machine need that computes 
>>this transformation if n is the size of the input? 

> Apparently, there are holes in my education---I'm more an engineer than
> a scientist. The complexity I'm used to computing on algorithms deals
> with time or number of operations; both the set and string algorithms
> seem linear to me.

And engineers don't have to know about space complexity of algorithms? :-) But time complexity is also different. The unary relation can be transformed in linear time, but the string transformation requires O(n.log(n)) steps.

> But if you won't bother to explain, no big deal.

I'll give you hint. For unnesting the string you need a counter. How much space will that counter take on the Turing tape. How much work, on average, will it take to increment that counter?

> I
> still say both operations are trivial to perform. And why draw the line
> at that particular place?

The linear-time constant-space transformation are traditionally seen as the class of computations that just do some reformatting but don't really compute anything new. Of course, this is to some extent a matter of taste and may under certain circumstances not be an appropriate definition, but if you look at what computations are in that class then it usually makes sense.

  • Jan Hidders
Received on Tue Jul 12 2005 - 23:11:52 CEST

Original text of this message