Re: Mark W. Hopkins theory perspective on parser engine technology?

On Mar 28, 11:58 am, Chris F Clark <c...@xxxxxxxxxxxxxxxxxxxx> wrote:
Tegiri Nenashi <TegiriNena...@xxxxxxxxx> writes:
I'm studying Mark W. Hopkins work on algebraic languages theory. What
are practical implications, for example, does representing an
arbitrary context-fee grammar as Kleene algebra C_2 (x) RX*  (or any
other embedding for that matter) make evident the existence of O^3
parsing algorithm (assuming that regular expressions parsing
complexity is O)? 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?

I laud your efforts.  There is much that appears interesting in his
approach.  However, he also reaches some results that are contrary to
established proofs.  For example, if I recall correctly, he claimed at
1 time to have a linear parsing algorithm for a general CFG, which is
well known to be O(n**2).  Since I couldn't get enough response out of
him to understand where the apparent contradiction lay, I gave up.

However, if you make progress on his work and want to discuss it.  I'd
be more than willing either in email or via posting.

Best regards,
-Chris

***************************************************************************­***
Chris Clark              Internet: christopher.f.cl...@xxxxxxxxxxxxxxxxxxxxxx
Compiler Resources, Inc.       or: comp...@xxxxxxxxxxxxx
23 Bailey Rd             Web Site:http://world.std.com/~compres ;
Berlin, MA  01503           voice:  (508) 435-5016
USA                           fax:  (978) 838-0263  (24 hours)
---------------------------------------------------------------------------­---

.