Problem for mathematically minded XML experts

[Rick Jelliffe]

Murata Makoto of FujiXerox  has been working on the question of set
operations on grammars for several years.

Rick Jelliffe

-----Original Message-----
From: Martin Bryan <mtbryan at sgml.u-net.com>
To: xml-dev at ic.ac.uk <xml-dev at ic.ac.uk>
Date: Saturday, 4 December 1999 16:24
Subject: Problem for mathematically minded XML experts


>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)
>


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)