This is a collection of postings from Fall 1997, augmented with other references in 1998. More recent references are provided in the database section "SGML/XML and non-deterministic ('ambiguous') content models."
See also the dissertation of Anne Brüggemann-Klein, Formal Models in Document Processing (1993). Several technical papers have been written by Anne Brüggemann-Klein [and Derick Wood] on ambiguity in SGML. For example: "One-Unambiguous Regular Languages" (1998). Similarly: Helena Ahonen, "Disambiguation of SGML Content Models," also published in the PODP '96 Proceedings. Also Andreas Neumann, "Unambiguity of SGML Content Models - Pushdown Automata Revisited," presented at the Third International Conference on the Developments in Language Theory (DLT'97) [biblio entry.]
Title: Re: Semantic of a Content Model
Author: davep@acm.org (David Peterson)
Date: Sat, 09 Aug 1997 21:06:56 -0400
In article <33E867CC.3235@PSI.Uni-Trier.DE>, Andreas Neumann
<neumann@PSI.Uni-Trier.DE> wrote:
> Suppose we have
>
> <!ELEMENT (a|b) - o EMPTY>
> <!ELEMENT x - - (a & b+)*>
>
> in the DTD, and
>
> <x><a><b><b><a></x>
>
> in the document instance.
> Is this supposed to be a valid instance of element x?
> Intuitively, it should be valid, but a precise look at section 11.2.4
> (Content models) shows:
>
> "The elements ... of the content ... must conform to the content
> model ... in the following order of priority:
> a) a repetition of the most recent satisfied token, if it has a
> rep or plus occurrence indicator; or
> b) some other token in a model group ..."
>
> Thus, after <a><b>, the second <b> can satisfy a new instance of b
> which has a plus occurrence indicator, but it could also start a new
> repetition of (a & b+). Since alternative a) has higher priority,
> only the b is repeated, and the following <a> starts a new instance
> of the whole &-group which cannot be fulfilled any more. But if
> alternative b) is chosen, the <a> completes the new instance of the
> &-group and everything is fine. However, for <x><a><b><b></x>, a)
> is the correct alternative.
And that is the correct answer. The second <a> starts the outer
repetition and a following <b> is required.
> Annex H.1 says that "and groups reduce to an or group of seq group
> permutations, for example (a & b) is equivalent to the regular
> expression ... ((a, b) | (b, a))", i.e. (a & b+)* is equivalent
> to ((a, b+) | (b+, a))*, which allows for <a><b><b><a> as well as
> <a><b><b>. Thus, both alternatives a) and b) must be considered
> (though the "annex does not form an integral part of" the SGML
> standard, it does express the intentions of the comittee and should
> help understanding the standard).
So when there's a conflict, Annex H loses.
Dave Peterson
SGMLWorks!
davep@acm.org
------------------------------
Title: Re: Semantic of a Content Model
Author: Lennart Staflin <lenst@lysator.liu.se>
Date: Sun, 10 Aug 1997 08:29:10 GMT
> In article <33E867CC.3235@PSI.Uni-Trier.DE>, Andreas Neumann
> <neumann@PSI.Uni-Trier.DE> wrote:
> > Annex H.1 says that "and groups reduce to an or group of seq group
> > permutations, for example (a & b) is equivalent to the regular
> > expression ... ((a, b) | (b, a))", i.e. (a & b+)* is equivalent
> > to ((a, b+) | (b+, a))*, which allows for <a><b><b><a> as well as
> > <a><b><b>. Thus, both alternatives a) and b) must be considered
> > (though the "annex does not form an integral part of" the SGML
> > standard, it does express the intentions of the comittee and should
> > help understanding the standard).
davep@acm.org (David Peterson) writes:
> So when there's a conflict, Annex H loses.
In this case it is not the annex that loses, but the interpretation
that the model ((a, b+) | (b+, a))* allows <a><b><b><a>. nsgmls thinks
the model is ambiguous. I would have thought that the repetion of b
takes priority over the repetion of the whole model group (The SGML
Handbook, 11.2.4, p412, lines 14--19).
--
Lennart Staflin <lenst@lysator.liu.se> /*/ (:ABSOLUTE :WILD)
--
Lennart Staflin <lenst@lysator.liu.se> /*/ (:ABSOLUTE :WILD)
----------
Title: Re: Semantic of a Content Model
Author: davep@acm.org (David Peterson)
Date: Sun, 10 Aug 1997 11:35:07 -0400
In article <m2afiqigq1.fsf@triton.lstaflin.pp.se>, Lennart Staflin
<lenst@lysator.liu.se> wrote:
> > In article <33E867CC.3235@PSI.Uni-Trier.DE>, Andreas Neumann
> > <neumann@PSI.Uni-Trier.DE> wrote:
> > > Annex H.1 says that "and groups reduce to an or group of seq group
> > > permutations, for example (a & b) is equivalent to the regular
> > > expression ... ((a, b) | (b, a))", i.e. (a & b+)* is equivalent
> > > to ((a, b+) | (b+, a))*, which allows for <a><b><b><a> as well as
> > > <a><b><b>. Thus, both alternatives a) and b) must be considered
> > > (though the "annex does not form an integral part of" the SGML
> > > standard, it does express the intentions of the comittee and should
> > > help understanding the standard).
>
> davep@acm.org (David Peterson) writes:
> > So when there's a conflict, Annex H loses.
My point was that the normative parts of the standard always win over
the non-normative parts.
> In this case it is not the annex that loses, but the interpretation
> that the model ((a, b+) | (b+, a))* allows <a><b><b><a>. nsgmls thinks
> the model is ambiguous. I would have thought that the repetion of b
> takes priority over the repetion of the whole model group (The SGML
> Handbook, 11.2.4, p412, lines 14--19).
I can't figure out why nsgmls would think the model ambiguous. As far
as I can tell, you "would have thought" correctly.
As I see it, if you start out in the <b>-first alternative, you can
wind up in the <a>-first alternative by having two <a>s in succession.
Once you are in the <a>-first alternative there is no way to get back
to the <b>-first alternative and two <a>s in succession will be an
error, as will ending with an <a>.
Dave Peterson
SGMLWorks!
davep@acm.org
--------------
Title: Re: Semantic of a Content Model
Author: roconnor@undergrad.math.uwaterloo.ca (Russell Steven Shawn O'Connor)
Date: Sun, 10 Aug 1997 19:47:00 GMT
In article <33E867CC.3235@PSI.Uni-Trier.DE>,
Andreas Neumann <neumann@PSI.Uni-Trier.DE> wrote:
>Annex H.1 says that "and groups reduce to an or group of seq group
>permutations, for example (a & b) is equivalent to the regular
>expression ... ((a, b) | (b, a))", i.e. (a & b+)* is equivalent
>to ((a, b+) | (b+, a))*, which allows for <a><b><b><a> as well as
Okay, after thinking about this for a bit, I did run the above ((a, b+) |
(b+, a))* through nsgmls to see what it did.
To my surprise it told me that this is an ambiguous content model</a>. I
understand why it thinks it is ambiguous. Given <a><b><b>...., after
reading the second <b> it can't tell if that <b> belongs to the first
part of the or connection, or the second part.
But what I don't understand is, why does it care? What is listed above is
a regular expression. All regular expressions can be parsed by a finite
state machine. There is no look ahead required when parsing with a
finite state machine. Anything that can be parsed by a finite state
machine is about as simple as it gets.
In fact, I already drawn the finite state machine required to determine if
a given series of <a> and <b>'s are satisfied by that regular expression
or not.
So again, why does nsgmls care that it can't determine which part of the
or connection it is in?
--
Russell O'Connor roconnor@uwaterloo.ca
<URL:http://www.undergrad.math.uwaterloo.ca/%7Eroconnor/>
"And truth irreversibly destroys the meaning of its own message"
-- Anindita Dutta, "The Paradox of Truth, the Truth of Entropy"
-----------
Title: Re: Semantic of a Content Model
Author: xeborduas@microstar.com (Eric Borduas)
Date: Mon, 11 Aug 1997 14:37:04 GMT
Andreas Neumann <neumann@PSI.Uni-Trier.DE> wrote:
>Dear SGML'ers,
>Suppose we have
> <!ELEMENT (a|b) - o EMPTY>
> <!ELEMENT x - - (a & b+)*>
>in the DTD, and
> <x><a><b><b><a></x>
>Annex H.1 says that "and groups reduce to an or group of seq group
>permutations, for example (a & b) is equivalent to the regular
>expression ... ((a, b) | (b, a))", i.e. (a & b+)* is equivalent
>to ((a, b+) | (b+, a))*, which allows for <a><b><b><a> as well as
><a><b><b>. Thus, both alternatives a) and b) must be considered
>(though the "annex does not form an integral part of" the SGML
>standard, it does express the intentions of the comittee and should
>help understanding the standard).
J K
<!ELEMENT x - -( (a, b+) | (b+, a) )* >
> <x><a><b><b><a></x>
-------J------- --K--
The sequence is: J(a) J(b) J(b) J(a)
& -> Both a and b must be present, only the order is not important.
In the example, <a><b><b> satisfies J and the last <a> partially
satisfies J, since both <a> and <b> must be present.
Also, SGML content models are not regular expressions. Although there
may be a regular expression that describes a content model, the rules
that govern their interpretation are not identical.
Klein and Klein & Wood have written papers on the validation of SGML
content models and their relationship to regular expressions. In
particular, "The Validation of SGML Content Models", Ann
Bruggemann-Klein and Derick Wood, March 23, 1993.
Eric Borduas
Microstar Software Ltd.
--------------------
Title: Re: Semantic of a Content Model
Author: papresco@calum.csclub.uwaterloo.ca (Paul Prescod)
Date: Mon, 11 Aug 1997 15:47:32 GMT
In article <EEpqyC.A9s@undergrad.math.uwaterloo.ca>,
Russell Steven Shawn O'Connor <roconnor@undergrad.math.uwaterloo.ca> wrote:
>So again, why does nsgmls care that it can't determine which part of the
>or connection it is in?
nsgmls cares because SGML cares. Annex H says:
"It can be shown (by Kleene's theorem) that a regular expression is equivalent
to a DFA. A parser could in theory, therefore, handle any model group by
reducing it to a regular expression and constructing a DFA with ... Practice,
however presents some difficulties.
One problem arises in the reduction of and groups. Since the number of required
seq group permutations is a factorial function, even small and groups can lead
to an intractably large number of corresponding seq groups. An and group with
six members for example would require 6! or 720 seq groups.
Another problem lies with the construction of the DFA. One method is first to
constract an NFA directly from the regular expression, then to derive a
deterministic equivalent. Although this and other algorithms for DFA
construction are non-polynomial and hardly intractable for the human-readable
models envisaged by SGML, they may be too resource-intensive for some
implementations.
This International Standard avoids these problems by eliminating the need to
construct a DFA. This it does by prohibiting models that are ambiguous or
require "look-ahead"....
As a result context checking can be done by simplified algorithms that use
only NFAs."
This restriction is hotly disputed and there is definately a camp that feels
that it should be removed. See the SGML Web Page under "special topics" and
"ambiguity" for more information.
Paul Prescod
-------------------
Title: Re: Semantic of a Content Model
Author: roconnor@undergrad.math.uwaterloo.ca (Russell Steven Shawn O'Connor)
Date: Mon, 11 Aug 1997 19:30:32 GMT
In article <EErAJ8.2p8@undergrad.math.uwaterloo.ca>,
Paul Prescod <papresco@calum.csclub.uwaterloo.ca> wrote:
>
>One problem arises in the reduction of and groups. Since the number of required
>seq group permutations is a factorial function, even small and groups can lead
>to an intractably large number of corresponding seq groups. An and group with
>six members for example would require 6! or 720 seq groups.
I thought NFA to DFA conversions were exponential function not factorial.
(That is to say if you have n states in an NFA, the DFA may have up to
2^n states.) Although this wouldn't change the argument very much.
Or is it saying that it requires a factorial algorithm to reduced a
DFA to a simpler form.
--
Russell O'Connor roconnor@uwaterloo.ca
<URL:http://www.undergrad.math.uwaterloo.ca/%7Eroconnor/>
"And truth irreversibly destroys the meaning of its own message"
-- Anindita Dutta, "The Paradox of Truth, the Truth of Entropy"
-----------
Title: Re: Semantic of a Content Model
Author: jenglish@crl2.crl.com (Joe English)
Date: 12 Aug 1997 11:50:22 -0700
Russell Steven Shawn O'Connor <roconnor@undergrad.math.uwaterloo.ca> wrote:
>
>Okay, after thinking about this for a bit, I did run the above ((a, b+) |
>(b+, a))* through nsgmls to see what it did.
>
>To my surprise it told me that this is an ambiguous content model. I
>understand why it thinks it is ambiguous. Given <a><b><b>...., after
>reading the second <b> it can't tell if that <b> belongs to the first
>part of the or connection, or the second part.
>
>But what I don't understand is, why does it care?
Because them's the rules:
"A _content model_ cannot be ambiguous; that is,
an element or character string that appears in the document
instance must be able to satisfy only one _primitive content
token_ without looking ahead in the document instance"
[ 11.2.4, "Ambiguous Content Model"; pp 414-415 ]
> What is listed above is
>a regular expression. All regular expressions can be parsed by a finite
>state machine. There is no look ahead required when parsing with a
>finite state machine. Anything that can be parsed by a finite state
>machine is about as simple as it gets.
>
>In fact, I already drawn the finite state machine required to determine if
>a given series of <a> and <b>'s are satisfied by that regular expression
>or not.
>
>So again, why does nsgmls care that it can't determine which part of the
>or connection it is in?
There are a couple of reasons. The principle reason cited
in Annex H is that the canonical algorithm for processing
regular expressions -- converting the R.E. to an NFA, then
converting that to a DFA -- is fairly expensive (it's worst-case
exponential). So, the reasoning goes, if content models
are required to be unambiguous (in the 8879 sense), a parser
can convert the content model to a deterministic finite automaton
in one step (with one state for each primitive content token and
transitions determined by the occurrence indicators and connectors).
This rationale isn't entirely compelling; there are after all
algorithms to match an input sequence against an NFA, or directly
against a regular expression. However, when you toss AND groups
into the mix these get expensive too (try building an NFA
for (a & b & c? & d? & e*) -- this is worse than exponential).
With the ambiguity restriction, AND groups are tractable;
without it they're much more difficult to deal with (but
probably not impossible).
The real show-stopper though is probably start-tag omission.
Without the ambiguity restriction, the formal definition of
"contextually required element" and related terms are utterly
meaningless. Specifically, the parts about "satisfied tokens":
in terms of general regular expressions it doesn't make any sense
to talk about _which_ subexpression an input token matches, only whether
the input sequence as a whole matches the regular expression
as a whole. This only makes sense for deterministic regular
expressions.
Consider:
<!ELEMENT foo - - (A, ((B,C)| B), D) -- this is ambiguous -->
...
<foo>
<a>...</a>
<b>...</b>
<!-- Here, is 'C', 'D', or neither of them contextually required?
Try to decide based on the text of the Standard.
-->
</foo>
--Joe English
jenglish@crl.com
--------------------
Title: Re: Semantic of a Content Model
Author: jenglish@crl2.crl.com (Joe English)
Date: 13 Aug 1997 10:58:35 -0700
Russell Steven Shawn O'Connor <roconnor@undergrad.math.uwaterloo.ca> wrote:
>Paul Prescod <papresco@calum.csclub.uwaterloo.ca> wrote:
>>
>>One problem arises in the reduction of and groups. Since the number of
>> required seq group permutations is a factorial function, even small and
>> groups can lead to an intractably large number of corresponding seq groups.
>> An and group with six members for example would require 6! or 720 seq
>> groups.
>
>I thought NFA to DFA conversions were exponential function not factorial.
>(That is to say if you have n states in an NFA, the DFA may have up to
>2^n states.)
That's correct. It's the conversion of an AND group with N nodes
to an NFA that produces N factorial states. (OR groups and SEQ groups
produce NFAs with N states).
James Clark has a nifty (though somewhat difficult to follow)
algorithm in SP; it treats AND groups just like repeatable
OR groups when constructing the automaton, then at parse time
it keeps track of an auxilliary "and state" which is a
vector of flags indicating which submodels of the AND
group have been satisfied. This takes O(N) space and
(I think) O(1) time per transition.
--Joe English
jenglish@crl.com
