Recognition and Parsing of Context-Free Languages in Time n^3

By Daniel H. Younger. 1967

Subfields: Computational Linguistics & Semantics, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Linguistics & Semantics

In Algorithms & Complexity

Citations in the corpus

Grammar-Based Grounded Lexicon Learning (2022, background): “G2L2 extends a standard dynamic programming algorithm for chart parsing (i.e., the CKY algo-rithm [24, 47, 11]) to compose sentence meaning from lexical meaning forms, based on syntax.”
Compositional Generalization and Natural Language Variation: Can a Semantic Parsing Approach Handle Both? (2020, methodology): “This enables efficient parsing using an algorithm similar to CKY (Cocke, 1969; Kasami, 1966; Younger, 1967) that does not require binarization of the grammar.”
Principles and Implementation of Deductive Parsing (1994, methodology): “The cache plays the same role as the chart in chart-parsing algorithms (Kay, 1986), the well-formed substring table in CYK parsing (Kasami, 1965; Younger, 1967), and the state sets in Earley's algorithm (Earley, 1970).”
Visually Grounded Compound PCFGs (2020, methodology): “Parsing seeks for the most probable parse t ∗ of w : Still, though the maximum a posterior (MAP) inference over p θ ( t | w ) can be solved by the CYK algorithm (Kasami, 1966; Younger, 1967), inference becomes intractable when introducing into z .”
Intrusion detection via static analysis (2001, methodology): “, the CYK, Earley, Tomita, and GLR techniques [37, 10, 16, 33]) uses bottom-up methods.”
ListOps: A Diagnostic Dataset for Latent Tree Learning (2018, methodology): “(2017) present uses a CYK-style (Cocke, 1969; Younger, 1967; Kasami, 1965) chart parser to compute a soft combination of all valid binary parse trees.”
Large Margin Methods for Structured and Interdependent Output Variables (2005, methodology): “…be written in the form of Equation (2), withΨ(x,y) denoting a histogram vector of counts (how often each grammar ruleg j occurs in the treey). f (x;w) can be efficiently computed by finding the structurey∈Y that maximizesF(x,y;w) via the CKY algorithm (Younger, 1967; Manning and Schuetze, 1999).”
The Algorithm Design Manual (2020, methodology): “The dynamic programming algorithm presented for parsing is known as the CKY algorithm after its three independent inventors (Cocke, Kasami, and Younger).”
Latent Tree Learning with Differentiable Parsers: Shift-Reduce Parsing and Chart Parsing (2018, background): “(2017) is based on chart parsing, and effectively works like a CKY parser (Cocke, 1969; Kasami, 1965; Younger, 1967) using a grammar with a single nonterminal A with rules A → A A and A → α, where α is any terminal.”
Span-based Semantic Parsing for Compositional Generalization (2020, methodology): “Furthermore, as i<j log c ′ exp [ s’ ( x i : j , c ′ )] does not depend on T at all, maximizing log p ( T ) is equivalent to maximizing the tree score: This scoring function can be maximized using CKY ( Cocke, 1969; Kasami, 1965; Younger, 1967).”
Unsupervised Latent Tree Induction with Deep Inside-Outside Recursive Auto-Encoders (2019, methodology): “We can extract the maximum scoring parse based on our single grammar rule using the CKY procedure (Kasami, 1966; Younger, 1967).”