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

RE: Adam Bosworth on XML and W3C

  • From: "Fuchs, Matthew" <matthew.fuchs@c...>
  • To: 'Tom Bradford' <bradford@d...>
  • Date: Tue, 09 Oct 2001 14:41:12 -0700

exponential processing time
Title: RE: Adam Bosworth on XML and W3C

Tom,

Information traversing the net is generated and consumed both by humans (carbon-based agents) and software (silicon-based agents) - I guess one could also say software and wetware.  Therefore design decisions about things like XML-Schema need to take both into account, as well as the fact that information is passing over the net in real-time among organizations.  I know people who'd really like to allow ambiguous content models, because that's easier for humans, but it has problems for our silcon-based friends.

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).  Given that I can send you something which may take exponential time to process, schemas or instances can be used for denial-of-service attacks.  I think he has the right model, but a schema language for XML on the Web can't use its full power, although it may have many applications within a single enterprise, or used in an offline manner.  Note that Relax NG doesn't use their full power either.  For more information on Murata-san's work, check out the Cover Pages - there're several articles, and it's a big toopic.

On the last point, there are various formal measures of complexity in computer science, such as big-O notation and Kolmogorov complexity.  Psychologists have obviously also been spending time trying to determine complexity measures for people.  It would be really great if there were some way to tie them together.  That way, people like me, involved in creating standards for both (XML Schema and Sox in my case), would have something a little more concrete than intuition to guide us (well, other people would - mine, of course, is infallible).

Better?

Matthew

> -----Original Message-----
> From: Tom Bradford [mailto:bradford@d...]
> Sent: Tuesday, October 09, 2001 11:39 AM
> To: Fuchs, Matthew
> Cc: 'Bullard, Claude L (Len)'; xml-dev@l...
> Subject: Re: Adam Bosworth on XML and W3C
>
>
> "Fuchs, Matthew" wrote:
> >
> > I think both are relevant - schema is consumed by both
> carbon and silicon
> > agents.  For two markup related examples - ambiguous
> content models and
> > Murata Makoto's work with hedge automata.  There seems to be a human
> > (carbon-based agent) predilection for ambiguous content
> models because they
> > can be easier to write, but they can cause problems for the
> behavior of
> > programs (silicon-based agents).  Likewise, Makoto's work
> is very elegant,
> > and implementation may not be so hard (low Kolmogorov
> complexity), but there
> > are cases requiring exponential processing time, which is
> why I was against
> > using them directly in Schema (when I heard "exponential" I thought
> > "denial-of-service attack").
> >
> > It would be awesome if there were some way to relate the
> formal complexity
> > measures with psychological complexity.  Do you know of any sources?
>
> Uhhh... Again in English, please?  Thanks.
>
> --
> Tom Bradford
> The dbXML Project
> Open Source Native XML Database
> http://www.dbxml.org
>


PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
 

Stylus Studio has published XML-DEV in RSS and ATOM formats, enabling users to easily subcribe to the list from their preferred news reader application.


Stylus Studio Sponsored Links are added links designed to provide related and additional information to the visitors of this website. they were not included by the author in the initial post. To view the content without the Sponsor Links please click here.

Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.