Re: CYK & Context-Free Expressions

On Apr 25, 3:21 pm, Rock Brentwood <markw...@xxxxxxxxx> wrote:
On Mar 27, 5:28 pm, Tegiri Nenashi <TegiriNena...@xxxxxxxxx> wrote:

Next, the CYK algorithm is essentuially a transitive
closure of a matrix. Given that matrix methods enjoy a lot of coverage
in Mr. Hopkins theory, perhaps there is a connection?

CYK and Earley are, respectively, the dynamic programming algorithms
for the so-called "bottom up parsing" and "top down parsing" -- which,
as per the terminology of the site you were referring to -- as the
special instances of the general translation problem for the canonical
bottom-up and top-down extensions of a grammar.

I fail to inderstand the significance of Earley algorithm. Before
going to Earley, however, let's stop at the CYK method for a moment.
Consider Fernando Pereira perspecive "Parsing as Deduction". Every
nonterminal S becomes a binary predicate S(x,y) written informally as
a statement: "The nonterminal S is valid at semiopen interval starting
at x and ended at y". Then, there is predicate join: S(x,y) & Q(y,z) -
T(x,z) corresponding to every grammar rule "T : S Q;". Therefore, we
arrived naturally to the concepts of transitive closure, shortest path
matrices, and so on. In addition, CYK algorithm naturally handles
ambiguity, and it doesn't introduce parse tree. One can build parse
tree on CYK artefacts (backpointers), but parse trees are not
fundamental. One can answer the questions like "is S(2,15) valid?", or
"what upper level symbols are derived from S(7,35)?" on the CYK matrix
alone.

There is one CYK puzzle that I fail see a satisfactory answer to.
Transitive closure could be algebraically written many ways:

lim (1+T)^n

1 + T + T^2 + T^3 + ...

(1+T) (1+T)^2 (1+T)^4 ...

corresponding to naive, seminaive, and other evaluation methods.
Applied to CYK, the fancier methods (like the third one in the above
list) fail. If we just evaluate binary powers of the reflective CYK
matrix and multiply them, we'll miss some derivations!

Now, what is the Earley method? Again, Pereira interprets it as a cute
mix of recursive descend with shift-reducing. That is not very
algebraic. It is also less intuitive, at least for me. How do we
handle ambiguity, and/or failure to recognize the full string?

Algebraic grammar methods school of thought emphasizes linear systems,
matrices and the related machinery. Therefore, I expected it to
embrace the CYK method much easier than Earley...

For an unambiguous grammar (that is: a grammar whose canonical
extensions are unambiguous), the output in both cases is, in effect,
itself a grammar; i.e. a grammar that recognizes the single word that
corresponds to the top-down or bottom-up construction sequence.

Extensions to ambiguous grammars generalize the output format so that
it can embody multiple sequences (i.e. multiple trees). Invariably,
this involves what's referred to as "node packing" and (for ambiguous
grammars) "cyclicity". The resulting format is equivalent to a context-
free grammar, itself. This corresponds to the fact that in the most
general case, the output upon translation of a single word is an
infinite set that, itself, is a context-free language. That is, the
(generally infinite) set of parses of a given word is a context-free
language, in its own right.

These constructs (forests,"node packing", etc) are too awkward to
genuinely believe for them to be the answer...

BTW, speaking of trees, what is algebraic definition of tree
structure?


.

Relevant Pages

  • Re: Does Valiant reduction make sense?
    ... CYK was married to LR-based technology by Tomita. ... already known as a context-free grammar. ... The corresponding context-free expression is ... the output for uv is an infinite set of parses whose ...
    (comp.theory)
  • Re: CYK & Context-Free Expressions
    ... going to Earley, however, let's stop at the CYK method for a moment. ... For each grammar a kind of universal CYK grammar formed along these ... Its complexity is O. ...
    (comp.theory)
  • Re: CYK & Context-Free Expressions
    ... list) fail. ... If we just evaluate binary powers of the reflective CYK ... Now given that optimization of the transitive closure fails to works, ... grammar where the only way to derive a word of length 4 may be ...
    (comp.theory)