An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages

By T. Kasami. 1965

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, methodology): “, the CKY algorithm [22, 45, 10]) to compose sentence meaning from lexical meaning forms, based on syntax.”
Automatically Solving Number Word Problems by Semantic Parsing and Reasoning (2015, background): “Figure 3: The DOL semantic parse tree for “Nine plus an integer is equal to 314” Figure 4: A syntactic parse tree 3.2.2 Parsing Parsing for CFG is a well-studied topic with lots of algorithms invented (Kasami, 1965; Earley, 1970).”
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.”
Learning Syntax from Naturally-Occurring Bracketings (2021, methodology): “The best scoring tree among all valid treesY can be found using the CKY algorithm (Cocke, 1969; Kasami, 1965; Younger, 1967).”
Span-based Semantic Parsing for Compositional Generalization (2020, methodology): “GEOQUERY Contains 880 questions about US geography (Zelle and Mooney, 1996), using the variable-free FunQL formalism from Kate et al. (2005). For the IID split, we use the standard train/test split, randomly sampling 10% of the training set for development.”
Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper) (2016, methodology): “The original inside algorithm applies to probabilistic context-free grammars in Chomsky Normal Form.”
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.”
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.”
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).”
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).”
Wide-Coverage Efficient Statistical Parsing with CCG and Log-Linear Models (2007, methodology): “The algorithm used to build the packed charts is the CKY chart parsing algorithm (Kasami 1965; Younger 1967) described in Steedman (2000).”
Learning to Compose Task-Specific Tree Structures (2017, methodology): “Unsupervised Tree-LSTM (Maillard et al., 2017) resolves this ambiguity while maintaining the soft property by introducing the concept of CYK parsing algorithm (Kasami, 1965; Younger, 1967; Cocke, 1970).”
Category-theoretic quantitative compositional distributional models of natural language semantics (2013, background): “CYK [15, 50, 89], Earley [25]), and a large number of corpora and other resources have been created to assist the learning of such generative grammars (e.”