Re: DTD Notation raises a question

[Paul Cody Johnston <pcj@inxar.org>]

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

Ron,

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

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