- From: Liam R E Quin <liam@w3.org>
- Date: Thu, 18 Oct 2012 13:03:42 -0400
- To: Michael Kay <mike@saxonica.com>
- Cc: xmlschema-dev@w3.org
On Thu, 2012-10-18 at 09:48 +0100, Michael Kay wrote: > In practice, enumerating the different permutations to permit all > possible orderings of 24 elements, some of which can be repeated, is > impossible on the kind of computers that are available for purchase > today, whatever the computer science theory might say. We faced this problem when I worked at SoftQuad - SGML had an "&" operator, and someone who wrote <!Element test - - (a & b & c & d & e & f & g & h & i)> found Author/Editor (and/or Rulesbuilder) needed 9! states in its finite state machine. Peter Sharpe gave a mathematician friend of his a week's stay on vacation at his home in exchange for a solution to the problem that operated in linear time, and this was incorporated into Author/Editor with considerable success. But it was not as simple as it might sound, because & interacted with all of the other operators and SGML rules, so e.g. you could write things like <!Element hopeless - - ((a | (b & (c|e))) & (d,a)+) -c> or even include #PCDATA in there... Liam -- Liam Quin - XML Activity Lead, W3C, http://www.w3.org/People/Quin/ Pictures from old books: http://fromoldbooks.org/ Ankh: irc.sorcery.net irc.gnome.org freenode/#xml The barefoot typographer - http://www.holoweb.net/~liam/
Received on Thursday, 18 October 2012 17:05:01 UTC