Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!

CYK algorithm

+ Save concept

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]

29 relations: Air Force Research Laboratory, Algorithm, Analysis of algorithms, Big O notation, Boolean matrix, Bottom-up parsing, Chomsky normal form, Computational complexity theory, Computational Intelligence (journal), Computer science, Context-free grammar, Coppersmith–Winograd algorithm, Courant Institute of Mathematical Sciences, Dynamic programming, Earley parser, Finite-state machine, GLR parser, Information and Computation, John Cocke, Journal of Computer and System Sciences, Journal of the ACM, New York University, Parse tree, Parsing, Parsing expression grammar, Probabilistic context-free grammar, Pseudocode, Tadao Kasami, The Art of Computer Programming.

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.

New!!: CYK algorithm and Air Force Research Laboratory · See more »


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

New!!: CYK algorithm and Algorithm · See more »

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.

New!!: CYK algorithm and Analysis of algorithms · See more »

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.

New!!: CYK algorithm and Big O notation · See more »

Boolean matrix

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

New!!: CYK algorithm and Boolean matrix · See more »

Bottom-up parsing

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

New!!: CYK algorithm and Bottom-up parsing · See more »

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.

New!!: CYK algorithm and Chomsky normal form · See more »

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.

New!!: CYK algorithm and Computational complexity theory · See more »

Computational Intelligence (journal)

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

New!!: CYK algorithm and Computational Intelligence (journal) · See more »

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.

New!!: CYK algorithm and Computer science · See more »

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.

New!!: CYK algorithm and Context-free grammar · See more »

Coppersmith–Winograd algorithm

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

New!!: CYK algorithm and Coppersmith–Winograd algorithm · See more »

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.

New!!: CYK algorithm and Courant Institute of Mathematical Sciences · See more »

Dynamic programming

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

New!!: CYK algorithm and Dynamic programming · See more »

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.

New!!: CYK algorithm and Earley parser · See more »

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.

New!!: CYK algorithm and Finite-state machine · See more »

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.

New!!: CYK algorithm and GLR parser · See more »

Information and Computation

Information and Computation is a computer science journal published by Elsevier (formerly Academic Press).

New!!: CYK algorithm and Information and Computation · See more »

John Cocke

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

New!!: CYK algorithm and John Cocke · See more »

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.

New!!: CYK algorithm and Journal of Computer and System Sciences · See more »

Journal of the ACM

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

New!!: CYK algorithm and Journal of the ACM · See more »

New York University

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

New!!: CYK algorithm and New York University · See more »

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.

New!!: CYK algorithm and Parse tree · See more »


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.

New!!: CYK algorithm and Parsing · See more »

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.

New!!: CYK algorithm and Parsing expression grammar · See more »

Probabilistic context-free grammar

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

New!!: CYK algorithm and Probabilistic context-free grammar · See more »


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

New!!: CYK algorithm and Pseudocode · See more »

Tadao Kasami

was a noted Japanese information theorist who made significant contributions to error correcting codes.

New!!: CYK algorithm and Tadao Kasami · See more »

The Art of Computer Programming

The Art of Computer Programming (sometimes known by its initials TAOCP) is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis.

New!!: CYK algorithm and The Art of Computer Programming · See more »

Redirects here:

CKY algorithm, CYK, CYK (algorithm), CYK parser, CYK-algorithm, Cocke-Kasami-Younger algorithm, Cocke-Younger-Kasami, Cocke-Younger-Kasami algorithm, Cyk algorithm, Cyk parser.


[1] https://en.wikipedia.org/wiki/CYK_algorithm

Hey! We are on Facebook now! »