OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.

 


Help: OASIS Mailing Lists Help | MarkMail Help

 


 

   Re: Why doesn't XML have Bag?

[ Lists Home | Date Index | Thread Index ]
  • From: Lars Marius Garshol <larsga@ifi.uio.no>
  • To: xml-dev@ic.ac.uk
  • Date: 27 Mar 1999 14:52:02 +0200


* Lars Marius Garshol 
|
| It is a limitation of DTDs and was introduced because without this
| operator element content models are easily mapped to finite state
| automatons, but the introduction of the '&' separator makes automaton
| generation much more difficult.

* Paul Janssens
| 
| Please correct me if I am wrong here but isn't that trivial?
| (you may get a BIG automaton, but it's not difficult to generate)

This is correct. However, the number of states required for n elements
is n! with this approach (ie: worse than exponential), which means
that the automaton doesn't just get BIG, for reasonably sized content
models it can get ABSOLUTELY MIND-BOGGLINGLY AWFULLY STUNNINGLY
HUGE. :)

To wit:

[24]> (! 10)
3628800
[25]> (! 30)
265252859812191058636308480000000
 
In other words, this approach doesn't work at all.

| and it's 'easily' visualised by the number of possible shortest
| paths between two opposing points on a hypercube.

I can think of easier ways of visualising it, though possibly not
'easier' ones. :)

--Lars M.


xml-dev: A list for W3C XML Developers. To post, mailto:xml-dev@ic.ac.uk
Archived as: http://www.lists.ic.ac.uk/hypermail/xml-dev/ and on CD-ROM/ISBN 981-02-3594-1
To (un)subscribe, mailto:majordomo@ic.ac.uk the following message;
(un)subscribe xml-dev
To subscribe to the digests, mailto:majordomo@ic.ac.uk the following message;
subscribe xml-dev-digest
List coordinator, Henry Rzepa (mailto:rzepa@ic.ac.uk)





 

News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS