Deterministic context free languages are the context free languages that can be accepted by a deterministic push down automata.

Deterministic context free languages can be recognized by a deterministic Turing machine in polynomial time.

The lower elementary functions are a subset of the elementary recursive functions.

Lower elementary recursive functions are limited to polynomial time growth.

From this is it correct to derive that deterministic push down automata are of equal power to the lower elementary recursive functions?

Edit: My reasoning is that because the deterministic context free languages can be recognized in polynomial time that a deterministic push down automata is implementing a boolean function of up to that complexity. The lower elementary functions are also up to polynomial time. As such are they not equal in power?

  • 3
    $\begingroup$ How exactly do you derive your statement from the givens? Try to use deductive logic, with a focus on definitions. $\endgroup$ – Yuval Filmus Mar 8 '16 at 22:54
  • 2
    $\begingroup$ A list of truths does not make a proof. $\endgroup$ – Raphael Mar 9 '16 at 1:10
  • $\begingroup$ I am not asking if this is a correct proof. It is not meant to be a proof. These are just facts that lead me to believe that they probably are equal in power. I have not been able to find the answer to this specific question online, and am asking if this is true or not. $\endgroup$ – 44701 Mar 9 '16 at 1:17

No, that doesn't follow at all. There are problems that can be solved in polynomial time, but that don't correspond to any deterministic context-free language.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.