[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*From*:**Joe English <jenglish@flightlab.com>***To*: xml-dev@lists.xml.org*Date*: Mon, 16 Jul 2001 12:30:09 -0700

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

**References**:**Re: DTD Notation raises a question***From:*Rod Davison <rdavison@sprint.ca>

**DTD Notation***From:*"Boyse, Jim" <Jim_Boyse@foremost.com>

**Re: DTD Notation raises a question***From:*Rod Davison <rdavison@sprint.ca>

**Re: DTD Notation raises a question***From:*John Cowan <jcowan@reutershealth.com>

- Prev by Date:
**RE: Historical I18n Note** - Next by Date:
**XML under JDK 1.0** - Previous by thread:
**Re: DTD Notation raises a question** - Next by thread:
**Synonyms and namespaces was: Re: DTD Notation raises a question** - Index(es):