[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] RE: Adam Bosworth on XML and W3C
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@C...] > Sent: Tuesday, October 09, 2001 3:59 PM > To: Fuchs, Matthew > Cc: 'Kohsuke KAWAGUCHI'; xml-dev@l... > Subject: RE: 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@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> > > >
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|