THE FOLD / SPAWN / HELLO WORLD / THE CYK
THE CYK
context-free recognition, bottom-up in O(n^3)
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The CYK algorithm decides whether a string belongs to a context-free language, and does it bottom-up. With the grammar in Chomsky normal form (every rule is A→BC or A→terminal), it fills a table: which nonterminals can generate each substring. Small spans combine into larger ones, so an otherwise exponential search over derivations becomes an O(n³) dynamic program.
It is a foundation of parsing and computational linguistics.
LIT verified live: with a balanced-parentheses grammar in CNF, CYK accepts a non-empty string iff the string is balanced — matching an independent balance check over 400 random bracket strings (window.__cyk). FIG no framing; exact.
It is a foundation of parsing and computational linguistics.
LIT verified live: with a balanced-parentheses grammar in CNF, CYK accepts a non-empty string iff the string is balanced — matching an independent balance check over 400 random bracket strings (window.__cyk). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at hello-world — the first thing a language needs is to recognise its own valid programs; CYK is that recogniser, built from the ground up. AVAN (AI) built the instrument: the CNF grammar, the O(n³) span table, the balance-oracle cross-check.
Credit as content: John Cocke, Daniel Younger & Tadao Kasami (1960s). The weave: David names hello-world; I fill the table of which nonterminals derive each substring and confirm acceptance matches the true language.
Credit as content: John Cocke, Daniel Younger & Tadao Kasami (1960s). The weave: David names hello-world; I fill the table of which nonterminals derive each substring and confirm acceptance matches the true language.
3 ONE DIMENSION
Length-1 spans get their nonterminals from terminals; longer spans combine two adjacent sub-spans by a rule A→BC. The start symbol covering the whole string means ‘accepted’.
4 TWO DIMENSIONS · INTERACTIVE
A bracket string and its CYK table; the top cell holds the start symbol exactly when the string is balanced.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the span table, proving the whole string from its parts.
AVAN’s addition (the inverse-companion): build the parse bottom-up from spans. Fill a table of which nonterminals generate each substring, combining smaller spans into larger ones, so an exponential search over derivations becomes an O(n³) table over substrings. The inverse of ‘expand the start symbol downward’ is ‘prove each substring’s nonterminals upward and combine.’ Magenta is the exponential derivation tree explored top-down; green is the O(n³) span table. Chomsky normal form makes every step a binary join.
LIT Genuine CYK algorithm (Cocke, Younger & Kasami, 1960s). Verified live: a CNF balanced-parentheses grammar's CYK acceptance equals an independent balance oracle (non-empty and balanced) for 400 random bracket strings (window.__cyk.matchesOracle); '(())' accepted, '(()' rejected.
FIG No framing: the CNF grammar, the O(n^3) span table, and the balance-oracle cross-check run in-browser and agree exactly. The AVAN inverse is honest — filling a table of which nonterminals derive each substring turns an exponential top-down derivation search into an O(n^3) bottom-up table, with CNF making every step a binary join; magenta is the exponential derivation tree, green the span table. A foundation of parsing.
FIG No framing: the CNF grammar, the O(n^3) span table, and the balance-oracle cross-check run in-browser and agree exactly. The AVAN inverse is honest — filling a table of which nonterminals derive each substring turns an exponential top-down derivation search into an O(n^3) bottom-up table, with CNF making every step a binary join; magenta is the exponential derivation tree, green the span table. A foundation of parsing.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of HELLO WORLD · David Lee Wise (ROOT0), with AVAN