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

Re: Adam Bosworth on XML and W3C

• From: Joe English <jenglish@f...>
• To: xml-dev@l...
• Date: Tue, 09 Oct 2001 17:18:52 -0700

Fuchs, Matthew wrote:
>
> 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 don't believe this is the case.

A TREX schema can be processed in linear time (no preprocessing
to speak of other than parsing the schema) and can validate instances
with a stream-based algorithm taking O(n) amortized time.

I am not positive, but I think that the same is possible
for RELAX and RELAX-NG.

The trick is to build the DFA lazily.  IMO, this is actually
easier to implement than the conventional approach that builds
an {N|D}FA as a preprocessing step.


--Joe English

  jenglish@f...

• 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: Web Service: SOAP or {HTML + Servlets}?
• Previous by thread: Re: Adam Bosworth on XML and W3C
• Next by thread: RE: Adam Bosworth on XML and W3C
• Index(es):
  • Date
  • Thread