References to deterministic time complexity of language classes

Question

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,

• In this diagram of the arithmetic hierarchy, it is claimed that $DCFL \in TIME(n^2)$ and $CFL \in TIME(n^6)$.
• The Wiki article for the Earley parser claims that deterministic CFGs can be parsed in $TIME(n)$, and general context-free grammars can be parsed in $TIME(n^3)$ much like the CYK algorithm.
• Some Stanford lecture slides I found claim that $DCFL \in TIME(n^2)$ while $CFL \in TIME(n^{18})$(?)

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?

Answer 1

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:

TIME($n^{18}$)

• 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.