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

["Fuchs, Matthew" <matthew.fuchs@commerceone.com>]

Murali,

I believe that is true for Relax but not for Makoto's original forest
automata work.  I quizzed him at length on this at dinner on the patio of a
lovely little restaurant in Antibes.  He was very insistent that worst case
complexity was exponential either for preprocessing the schema or validating
the instance, take your pick, and that bottom-up tree automata are strictly
more powerful than top-down.  This was very important to me, as I was
interested in seeing how much of his work could be included in Schema.

Had he insisted instead that they were both polynomial (and I know the
difference), XML Schema might be a very different beast today.  If this
doesn't make sense, ask Makoto what he thought I was asking.

Matthew

> -----Original Message-----
> From: Murali Mani [mailto:mani@CS.UCLA.EDU]
> Sent: Tuesday, October 09, 2001 3:59 PM
> To: Fuchs, Matthew
> Cc: 'Kohsuke KAWAGUCHI'; xml-dev@lists.xml.org
> Subject: RE: [xml-dev] Adam Bosworth on XML and W3C
> 
> 
> 
> 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>
> >
>