Timeline for References to deterministic time complexity of language classes
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 23, 2021 at 2:24 | answer | added | rici | timeline score: 1 | |
| Nov 22, 2021 at 17:09 | comment | added | Emil Jeřábek | 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. | |
| S Nov 22, 2021 at 16:09 | review | First questions | |||
| Nov 23, 2021 at 6:40 | |||||
| S Nov 22, 2021 at 16:09 | history | asked | user145559 | CC BY-SA 4.0 |