RELAX NG

What Is Ambiguity?

First, I will clarify the concepts of ambiguity and determinism. They’re blurred in many papers and discussions, yet aren’t as obscure as people often think.

Ambiguity Versus Determinism

The first distinction is the difference between ambiguity and determinism. These two terms have been given precise definitions by regular expressions and hedge grammar theoreticians, and in this chapter I will follow the usage of these terms as defined by Murata Makoto. Part of the confusion about these notions comes from their frequent misuse.

A schema is said to be ambiguous when a document may be valid when its contents match multiple different pattern alternatives. A trivial example is:

 element foo{empty} | element foo{empty}

When an empty element named foo is found in an instance document, there is no way to say whether it is valid per the left definition or the right definition of element foo{empty} in the schema.

There are, of course, more complex cases of ambiguity, and you’ll see some of them in the next sections. Still, this is the general idea behind ambiguity.

Ambiguity is independent of any implementation or algorithm. It’s a property of the schema itself; a schema is either ambiguous or not ambiguous.

Determinism has been introduced to facilitate the implementation of schema processors. The basic idea behind determinism is that at each point, when matching an instance document against a schema, the schema processor has at most one possible choice. This makes life easier ...