It's fairly well known that $REG \in TIME(n)$. I would like to know similar inclusions for the language classes $DCFL$ and $CFL$.

I have found a variety of claims for these classes on the internet. For instance,

I was taught that $CFL \in TIME(n^3)$ due to the fact that the CYK algorithm parses in time $O(n^3)$. Does anyone have references to the original time complexity results for these language classes?

  • $\begingroup$ The linked Wikipedia article on the Earley parser gives a reference to the original paper by Earley. Did you check it? Also, $\mathrm{DCFL\subseteq DTIME}(n)$ (and $\mathrm{CFL\subseteq NTIME}(n)$) is essentially trivial from the definition: a DPDA consumes each input letter in $O(1)$ time, hence it runs in $O(n)$ time in total. $\endgroup$ Nov 22 at 17:09

Did you read the slides in the Stanford course? A key point is that it is discussing time complexity for a Turing Machine (TM). Turing Machines are only polynomially equivalent in time complexity to general computers. The precise relationship is found in the slide (in bold for convenience): What it says is:


  • All CFLs are in TIME($n^{18}$)
    • Given a grammar $G$, there exists an algorithm on a standard computer that can decide whether $G$ generates $w$ in time TIME(${n^3}$).
    • Since an $f(n)$-time computer program can be simulated in time $O(f(n)^6)$ on a TM, this means all CFLs are in TIME($n^{18}$)).

Of course, that's a loose bound, since it's based on a general model for converting a computer program into a TM. The graphic presents a tighter bound, but also for DTIME, which is: (again, emphasis added)

the computational resource of computation time for a deterministic Turing machine.

In short, there is no contradiction here. You need to read the complexities in the context of the computational model being used. And remember that they are just upper bounds on the complexity.


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.