OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

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

Re: DTD Notation raises a question

> 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").
> we can do this is certain restricted cases.
> (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.


Perhaps I don't fully understand your question because this seems to
be pretty simple.  As far as I;m concerned, two content models are
equivalent if they are graph isomorphic, a fancy way of saying that
they produce the same parse tree.  Parentheses in regular expressions
are used to explicilty define the precedence of subexpressions in the
string.  Since the natural precedence of the operators (*, +, ?, |) is
known, you can always determine if two content models are "synonymous"
by simply parsing them.

The exception to this is that various xml processors handle so called
"non-deterministic" content models differently; some reject them while
others accept.  There was a thread on this just a few days ago.

Am I missing something in your question?


| Paul Johnston | pcj@inxar.org | http://inxar.org |