CFG Recognition: Difference between revisions

Revision as of 13:04, 15 February 2023

Given a grammar $G$ and a string $s$, determine if the string $s$ can be derived by the grammar $G$.

n: length of the given string

Name	Year	Time	Space	Approximation Factor	Model	Reference
Cocke–Younger–Kasami algorithm	1968	G\|)$	$O(n^{2})$	Exact	Deterministic	Time & Space
Valiant	1975	G\|)$ where omega is the exponent for matrix multiplication	$O(n^{2})$?	Exact	Deterministic	Time

Error creating thumbnail: Unable to save thumbnail to destination

Error creating thumbnail: Unable to save thumbnail to destination

Error creating thumbnail: Unable to save thumbnail to destination

Problem	Implication	Year	Citation	Reduction
k-Clique	assume: k-Clique Hypothesis then: there is no $O(N^{\omega-\epsilon}) time algorithm for target for any $\epsilon > {0}$	2017	https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/abstract/document/8104058	link
k-Clique	assume: k-Clique Hypothesis then: there is no $O(N^{\{3}-\epsilon}) time combinatorial algorithm for target for any $\epsilon > {0}$	2017	https://ieeexplore-ieee-org.ezproxy.canberra.edu.au/abstract/document/8104058	link

@@ Line 26: / Line 26: @@
 |}
-== Time Complexity graph ==
+== Time Complexity Graph ==
 [[File:CFG Problems - CFG Recognition - Time.png|1000px]]
-== Space Complexity graph ==
+== Space Complexity Graph ==
 [[File:CFG Problems - CFG Recognition - Space.png|1000px]]
-== Pareto Decades graph ==
+== Pareto Frontier Improvements Graph ==
 [[File:CFG Problems - CFG Recognition - Pareto Frontier.png|1000px]]