0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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
    Commented Mar 8, 2016 at 22:54
  • 2
    $\begingroup$ A list of truths does not make a proof. $\endgroup$
    – Raphael
    Commented Mar 9, 2016 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
    Commented Mar 9, 2016 at 1:17

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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