Equivalence of P, AL and multi-head pushdown automata

From: kve adelphia net ("kve)
Date: 12/11/04 

Date: Fri, 10 Dec 2004 23:25:46 -0500

Hi all,

I have been looking at problem 10.10 in Sipser's theory of computation
text. It asks for a proof that the class of languages recognized by
deterministic multi-head pushdown automata is equal to P. As a hint, it
points out that P = AL (alternating log-space). I think I know how to
show that an arbitrary log-space ATM can be simulated by a multi-head
DPDA, but I'm having trouble seeing how to go in the other direction.
Any hints would be appreciated.

I've looked at Cook's paper "Characterizations of Pushdown Machines in
Terms of Time-Bounded Computers", which gives this result along with a
number of other correspondences of machine models. Unfortunately, at a
crucial point in the argument he cites without explication "unpublished
but fairly well-known proof techniques by Alan Cobham and others".
Well, this is apparently not well-known amongst undergrad CS students,
but perhaps that's what makes it a good exercise.

One other question: It seems striking to me that multi-head PDAs give a
way to characterize P without any explicit reference to a time bound.
Is there anything similar for the class NP?

Thanks in advance,
   Kurt