If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser (Q4562283): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Changed an Item
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Losing Weight by Gaining Edges / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Minimum Distance Error-Correcting Parser for Context-Free Languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5452362 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4249533 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3549649 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The monotone circuit complexity of Boolean functions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4705344 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Sparse RNA folding: time and space efficient algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5110876 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Hardness of RNA Folding Problem With Four Symbols. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tight lower bounds for certain parameterized NP-hard problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Strong computational lower bounds via parameterized complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: On certain formal properties of grammars / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5657644 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3651735 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Biological Sequence Analysis / rank
 
Normal rank
Property / cites work
 
Property / cites work: An efficient context-free parsing algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the complexity of fixed parameter clique and dominating set / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the role of error productions in syntactic error correction / rank
 
Normal rank
Property / cites work
 
Property / cites work: Powers of tensors and fast matrix multiplication / rank
 
Normal rank
Property / cites work
 
Property / cites work: Recognition time of context-free languages by on-line Turing machines / rank
 
Normal rank
Property / cites work
 
Property / cites work: An Improved Context-Free Recognizer / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Computational Complexity of Algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Clique is hard to approximate within \(n^{1-\epsilon}\) / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the Parsing of Deterministic Languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: How Hard Is It to Approximate the Best Nash Equilibrium? / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4506483 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Large Cliques Elude the Metropolis Process / rank
 
Normal rank
Property / cites work
 
Property / cites work: Reducibility among Combinatorial Problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the translation of languages from left to right / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4054657 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fast context-free grammar parsing requires fast boolean matrix multiplication / rank
 
Normal rank
Property / cites work
 
Property / cites work: Approximately matching context-free languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3688439 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Edit Distance with Duplications and Contractions Revisited / rank
 
Normal rank
Property / cites work
 
Property / cites work: An Error Correcting Parser for Context Free Grammars that Takes Less Than Cubic Time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4197337 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fast recognition of pushdown automaton and context-free languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Context-free recognition via shortest paths computation: a version of Valiant's algorithm / rank
 
Normal rank
Property / cites work
 
Property / cites work: A simplified lower bound for context-free-language recognition / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3392275 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Gaussian elimination is not optimal / rank
 
Normal rank
Property / cites work
 
Property / cites work: General context-free recognition in less than cubic time / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient algorithms for clique problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: A new algorithm for optimal 2-constraint satisfaction and its implications / rank
 
Normal rank
Property / cites work
 
Property / cites work: Faster all-pairs shortest paths via circuit complexity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Multiplying matrices faster than coppersmith-winograd / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parameterized and Exact Computation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Open problems around exact algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Recognition and parsing of context-free languages in time n3 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An improved combinatorial algorithm for Boolean matrix multiplication / rank
 
Normal rank

Revision as of 17:10, 17 July 2024

scientific article; zbMATH DE number 6995738
Language Label Description Also known as
English
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
scientific article; zbMATH DE number 6995738

    Statements

    If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser (English)
    0 references
    0 references
    0 references
    19 December 2018
    0 references
    CFG parsing
    0 references
    Dyck edit distance
    0 references
    RNA folding
    0 references
    conditional lower bounds
    0 references
    context-free grammars
    0 references
    Valiant's algorithm
    0 references
    clique algorithms
    0 references
    hardness in P
    0 references
    combinatorial algorithms
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references