Re: CYK & Context-Free Expressions

On May 1, 4:48 pm, Rock Brentwood <markw...@xxxxxxxxx> wrote:
On Apr 28, 12:58 pm, Tegiri Nenashi <TegiriNena...@xxxxxxxxx> wrote:

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) -

For each grammar a kind of universal CYK grammar formed along these
lines. If you think in terms of matrices then for each rule
   q -> z1 z2 ... zn
and each i0 <= i1 <= ... <= in, one has a set of rules
   q(i0,in) -> z1(i0,i1) z2(i1,i2) ... zn(i_{n-1} in).
For each terminal x, and each i, one has
   x(i,i+1) -> x.

Wait a minute, speaking of CYK, don't you need to put grammar into CNF
first? The expression

q(i0,in) -> z1(i0,i1) z2(i1,i2) ... zn(i_{n-1}

certainly looks like a term from matrix product, but technically what
is result of multiplying z1(i0,i1) z2(i1,i2)? There is no variable in
the grammar for it.

When including an output alphabet Y then for each y in Y, one also has
the rule
   y(i,i) -> y.

The CYK algorithm, itself, is then a method of winnowing down the
minimal subset of these rules that processes a given input. One finds
all the A(i,i+D) for D = 0 and for all terminals and non-terminals A;
then the same for D = 1, then for D = 2.

The result is, itself, a grammar. Its complexity is O(n^{k+1}).

I see. You try all combinations of the binded summation indexes in the
above expression

q(i0,in) -> z1(i0,i1) z2(i1,i2) ... zn(i_{n-1}

hence the complexity O(n^{k+1})...

.

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
    ... CYK and Earley are, respectively, the dynamic programming algorithms ... I fail to inderstand the significance of Earley algorithm. ... and it doesn't introduce parse tree. ... Algebraic grammar methods school of thought emphasizes linear systems, ...
    (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)