Re: DTD Notation raises a question

[Joe English <jenglish@flightlab.com>]

On Wed, 11 Jul 2001, Rod Davison wrote:

> given two markup definitions
>
> <!ELEMENT  x  (contentmodel_1) >
> <!ELEMENT  x  (contentmodel_2) >
>
> such that the two content models (assuming normalized strings) are not
> string-equal; is it possible to determine if the two content_models describe
> exactly the same set of structures.  (i.e are they "synonyms").

Yes.  The usual way of doing this is to construct the
minimal DFA for each content model and check if the DFAs
are isomorphic.  (This works because the minimal DFA for
a regular language is unique up to isomorphism).  You
can also construct a bisimulation (or attempt to construct one --
I forget the exact details) on the two content models
to test if one is a subset of the other or compute the
union, intersection, and/or difference of their respective
languages.

> (a , b*, c*) is synonymous to  ((a) , (b)*, (c)*)
>
> but can we generalize this to a set of transformations that can be applied to
> one to produce the other.  And if we can, is such a process decidable?
> Specifically, I am looking at whether or not this pocess can be algorithmized
> .

This one I'm not sure about.  There are plenty of algebraic
identities which can be exploited ('|' and ',' are associative,
'|' is commutative, the distributive law (a, (b|c)) = ((a,b) | (a,c)),
etc.) to help check things like this "by hand", but I don't
know if the process can be automated or not.


--Joe English

  jenglish@flightlab.com