CFG Recognition: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 31: | Line 31: | ||
[[File:CFG Problems - CFG Recognition - Time.png|1000px]] | [[File:CFG Problems - CFG Recognition - Time.png|1000px]] | ||
== Reductions FROM Problem == | == Reductions FROM Problem == | ||
Latest revision as of 09:09, 28 April 2023
Description
Given a grammar $G$ and a string $s$, determine if the string $s$ can be derived by the grammar $G$.
Related Problems
Related: CFG Parsing
Parameters
$n$: length of the given string
$|G|$: size of the grammar
Table of Algorithms
| 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 |
Time Complexity Graph
Error creating thumbnail: Unable to save thumbnail to destination
Reductions FROM Problem
| 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 |
References/Citation
https://linkinghub-elsevier-com.ezproxy.canberra.edu.au/retrieve/pii/S0022000075800468