Problem for mathematically minded XML experts

[Martin Bryan]

I would like to pose the following question to those of you with a
mathematical bent who have some spare time (I'm not expecting the answer
quickly - this is a holiday teaser I suspect!).

Given I have two DTDs, in which there are two elements whose models can be
described as follows:

Element DTD1 consists of a sequence of E1 elements and G1 OR groups, where
the total number of elements in the OR groups is N1

and

Element DTD2 consists of a sequence of E2 elements and G2 OR groups, where
the total number of elements in the OR groups is N2

is there a formula that can be used to determine whether the same pair of
elements are valid in both DTD1 and DTD2? If there is, is there a way to
determine the difference caused by the following conditions being added:

a) there need be no constraint on the order of the elements
b) the elements must be in a particular order
c) the elements must be adjacent, in any order
d) the elements must be adjacent, in a particular order.

Does the split of the number of elements in each OR group affect the
calculation significantly?
Does the fact that one or other, or both of the elements is a member of a
group significantly affect the calculation?
How would the calculation change if it was required that three matches were
required from the model?

If you can help me understand any part of the problem, or point me to a
paper/book on the subject, I would be grateful.

Martin Bryan, 29 Oldbury Orchard, Churchdown, Glos GL3 2PU, UK
Phone/Fax: +44 1452 714029 E-mail: mtbryan at sgml.u-net.com



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