[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Re: DTD Notation raises a question
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@f...
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|