Recognition and parsing of context-free languages in time n3

1967/02/01 by D. H. Younger, Daniel H. Younger · 12 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Artificial intelligence #Bottom-up parsing #Computer science #Context (archaeology) #Context-free language #DNA and Biological Computing #History #Natural language processing #Parsing #Programming language #Rule-based machine translation #Top-down parsing #semigroups and automata theory

paper · doi:10.1016/s0019-9958(67)80007-x

crossref issued 1967/02/01 · crossref published 1967/02/01 · crossref published-print 1967/02/01 · openalex publication_date 1967/02/01 · crossref created 2005/03/11 · crossref deposited 2019/01/28 · openalex created_date 2025/10/10 · crossref indexed 2026/06/30 · openalex updated_date 2026/07/15

Citations

• On certain formal properties of grammars

Cited by

• RECOGNITION CAN BE HARDER THAN PARSING
• Products of weighted logic programs
• Framework and Resources for Natural Language Parser Evaluation
• Analyzing Context-Free Grammars Using an Incremental SAT Solver
• From Historical Puzzles to Grammatical Constraints: Circular Partitions, Generalized Run-Length Encodings, and Polynomial-Time Decidability
• Heads-up! Unsupervised Constituency Parsing via Self-Attention Heads
• Boolean grammars
• R2D2: Recursive Transformer based on Differentiable Tree for Interpretable Hierarchical Language Modeling
• Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
• Oracle Pushdown Automata, Nondeterministic Reducibilities, and the CFL Hierarchy over the Family of Context-Free Languages
• A general context-free parsing algorithm running in linear time on every LR(k) grammar without using lookahead
• CYK algorithm [wikipedia]