RE: [xml-dev] Adam Bosworth on XML and W3C

[Murali Mani <mani@CS.UCLA.EDU>]

Dear Matthew,

Parsing is linear -- Makoto has said this over and over again -- Kohsuke
is the one who has implemented several of the algorithms.

Checking validity of a regular tree grammar as well as type assignment
have polynomial time algorithms.

cheers and regards - murali.

On Tue, 9 Oct 2001, Fuchs, Matthew wrote:

> Ask Makoto - this is what he told me, and I didn't see any reason to doubt
> his veracity about his own work.  By the way, if one looks closely one
> notices that XDuce, the basis for Trex, is really a reproduction of Makoto's
> work from another direction, so XDuce should suffer the same issues (common
> to type-inference systems).
>
> Matthew
>
> > -----Original Message-----
> > From: Kohsuke KAWAGUCHI [mailto:kohsukekawaguchi@yahoo.com]
> > Sent: Tuesday, October 09, 2001 3:01 PM
> > To: Fuchs, Matthew; xml-dev@lists.xml.org
> > Subject: Re: [xml-dev] Adam Bosworth on XML and W3C
> >
> >
> >
> > > I mentioned Murata Makoto's brilliant work with
> > forest-automata as an
> > > expanded model for markup is that to gain the full
> > expressive power of his
> > > work one needs to accept (in the worst case) bottom-up
> > parsing (eliminates
> > > stream-based applications) and either exponential-time
> > preprocessing (merely
> > > processing an unknown schema may be prohibitively expensive) or
> > > exponential-time validation (there are some schemas for
> > which parsing is
> > > effectively impossible).
> >
> > This is very interesting. Would you please show me an example that
> > causes exponential-time compilation or validation?
> >
> >
> > regards,
> > ----------------------
> > K.Kawaguchi
> > E-Mail: kohsukekawaguchi@yahoo.com
> >
>
> -----------------------------------------------------------------
> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
> initiative of OASIS <http://www.oasis-open.org>
>
> The list archives are at http://lists.xml.org/archives/xml-dev/
>
> To subscribe or unsubscribe from this elist use the subscription
> manager: <http://lists.xml.org/ob/adm.pl>
>