CFG Recognition (CFG Problems)
Jump to navigation
Jump to search
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
Space Complexity Graph
Time-Space Tradeoff
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/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/abstract/document/8104058 | link |
References/Citation
https://linkinghub.elsevier.com/retrieve/pii/S0022000075800468