[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

RE: Adam Bosworth on XML and W3C

• From: Murali Mani <mani@C...>
• To: "Fuchs, Matthew" <matthew.fuchs@c...>
• Date: Tue, 09 Oct 2001 15:58:50 -0700 (PDT)

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@y...]
> > Sent: Tuesday, October 09, 2001 3:01 PM
> > To: Fuchs, Matthew; xml-dev@l...
> > Subject: Re:  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@y...
> >
>
> -----------------------------------------------------------------
> 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>
>

• References:
  • RE: Adam Bosworth on XML and W3C
    • From: "Fuchs, Matthew" <matthew.fuchs@c...>

• Prev by Date: Re: Adam Bosworth on XML and W3C
• Next by Date: RE: Re: Adam Bosworth on XML and W3C
• Previous by thread: RE: Adam Bosworth on XML and W3C
• Next by thread: RE: Adam Bosworth on XML and W3C
• Index(es):
  • Date
  • Thread