Communication
Install
Faster access than browser!

# CYK algorithm

In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars, named after its inventors, John Cocke, Daniel Younger and Tadao Kasami. [1]

## Air Force Research Laboratory

The Air Force Research Laboratory (AFRL) is a scientific research organization operated by the United States Air Force Materiel Command dedicated to leading the discovery, development, and integration of affordable aerospace warfighting technologies, planning and executing the Air Force science and technology program, and providing warfighting capabilities to United States air, space, and cyberspace forces.

## Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

## Analysis of algorithms

In computer science, the analysis of algorithms is the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them.

## Big O notation

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

## Boolean matrix

In mathematics, a Boolean matrix is a matrix with entries from a Boolean algebra.

## Bottom-up parsing

In computer science, parsing reveals the grammatical structure of linear input text, as a first step in working out its meaning.

## Chomsky normal form

In formal language theory, a context-free grammar G is said to be in Chomsky normal form (first described by Noam Chomsky) if all of its production rules are of the form: where A, B, and C are nonterminal symbols, a is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε denotes the empty string.

## Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

## Computational Intelligence (journal)

Computational Intelligence is a peer-reviewed scientific journal covering research on artificial intelligence.

## Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

## Context-free grammar

In formal language theory, a context-free grammar (CFG) is a certain type of formal grammar: a set of production rules that describe all possible strings in a given formal language.

In linear algebra, the Coppersmith–Winograd algorithm, named after Don Coppersmith and Shmuel Winograd, was the asymptotically fastest known matrix multiplication algorithm until 2010.

## Courant Institute of Mathematical Sciences

The Courant Institute of Mathematical Sciences (CIMS) is an independent division of New York University (NYU) under the Faculty of Arts & Science that serves as a center for research and advanced training in computer science and mathematics.

## Dynamic programming

Dynamic programming is both a mathematical optimization method and a computer programming method.

## Earley parser

In computer science, the Earley parser is an algorithm for parsing strings that belong to a given context-free language, though (depending on the variant) it may suffer problems with certain nullable grammars.

## Finite-state machine

A finite-state machine (FSM) or finite-state automaton (FSA, plural: automata), finite automaton, or simply a state machine, is a mathematical model of computation.

## GLR parser

A GLR parser (GLR standing for "generalized LR", where L stands for "left-to-right" and R stands for "rightmost (derivation)") is an extension of an LR parser algorithm to handle nondeterministic and ambiguous grammars.

## John Cocke

John Cocke (May 30, 1925 &ndash; July 16, 2002) was an American computer scientist recognized for his large contribution to computer architecture and optimizing compiler design.

## Journal of Computer and System Sciences

The Journal of Computer and System Sciences (JCSS) is a peer-reviewed scientific journal in the field of computer science.

## Journal of the ACM

The Journal of the ACM is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects.

## New York University

New York University (NYU) is a private nonprofit research university based in New York City.

## Parse tree

A parse tree or parsing tree or derivation tree or concrete syntax tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar.

## Parsing

Parsing, syntax analysis or syntactic analysis is the process of analysing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar.

## Parsing expression grammar

In computer science, a parsing expression grammar, or PEG, is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language.

## Probabilistic context-free grammar

Grammar theory to model symbol strings originated from work in computational linguistics aiming to understand the structure of natural languages.

## Pseudocode

Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm.