Prev: TAUTOLOGY and SAT
Next: Resurrecting out-of-print math books
From: Dillon on 13 Jul 2008 20:10
Hi,

Consider a linear bounded pushdown automata (LBPDA) for which the size of
the stack is bounded by some constant multiple of the length of the input.
Is LBPDA's expressive power weaker than that of a normal PDA (i.e. a LBPDA
cannot express some languages that can be done by a PDA)? Or, do both of
these two computation model have the same expressive power? (Let's just
assume that both are nonderministic.)

Thanks,
Dillon


 | 
Pages: 1
Prev: TAUTOLOGY and SAT
Next: Resurrecting out-of-print math books