Re: Guarded normal form (part 1)

[Murata Makoto <mura034@attglobal.net>]

James Clark wrote:
 
> 1. How does your duplicate attribute restriction deal with attributes that
> have a name class other than a single name?  (I think I have a simple
> algorithm to detect whether intersection of two name-classes is non-empty.)

This is not as easy as I first thought.  For example, if a guard has 
three <attribute> patterns shown below, there are no conflicts.

<attribute>
   <choice>
      <name>a</name>
      <name>b</name>
   </choice>
</attribute> 

<attribute>
   <choice>
      <name>b</name>
      <name>c</name>
   </choice>
</attribute>

<attribute>
   <choice>
      <name>c</name>
      <name>a</name>
   </choice>
</attribute>

However, I think that there is a simple algorithm.  It has two steps: 
elimination and backtracking.

1) elimination

If an <attribute> contains either <t:anyName/> or 
<t:nsName ns="namespaceURI"/> and its occurrence is not in the 
first child of <difference>, that <attribute> element can be 
satisified without causing any conflicts with other <attribute> 
patterns.  For example, the following <attribute> patterns in a 
guard do not conflict with other <attribute> patterns in the guard.

<attribute><anyName/></attribute>

<attribute><choice><nsName ns="namespaceURI"/><name>NCName</name></choice></attribute>

Therefore, we can eliminate such <attribute> patterns and concentrate 
on remaining <attribute> patterns.  The set of names matching such an 
<attribute> pattern is a FINITE set of URI+localName pairs.

2) backtracking

Each <attribute> element has a finite set of possibilitites.  We 
have to examine them in sequence by backtracking.  After choosing 
one possiblity for one <attribute>, we pick another <attribute> 
pattern and choose one possibility.  If no possiblities are found, 
we backtrack.  If no possibilities are found, this guard cannot 
be satisfied.

Usually, each <attribute> has a only one possibility, and thus 
backtraking does not cause exhaustive search.

Cheers,

Makoto