canonical representation of NC.

[Kohsuke KAWAGUCHI <kohsuke.kawaguchi@eng.sun.com>]

It is basically the same algorithm that you've introduced (though mine
is less cooked, as I wrote). It computes

- equivalence/subset relationship between multiple NCs.
- the canonical representation of NC.
  It is useful to write the result of computation back to XML
  representation.


> PosSet< foo{Pos}<a,b,c> >

This notation is canonicalized; that is, 

- any NC can be written in this notation.
- two NCs that results in the same notation are the equivalent.

And this notation is closed to boolean operations. So you can apply as
much operations as you want and you'll still get the smallest NC
representation.


It is very close to your "possibleNames" algorithm. possibleNames
doesn't hold Pos/Neg information. Yours just keep name pairs and let NC
compute acceptability, whereas my notation holds acceptability
information as well as name pairs.


If canonicalize(NC) => PosSet< foo{Pos}<a,b,c> > , then it can be also
written by your possibleNames algorithm as

possibleNames(NC) => { (foo,a), (foo,b), (foo,c) }


If canonicalize(NC) => NegSet< foo{Neg}<a> >, then
possibleNames(NC) => {(MAGIC,MAGIC), (foo,MAGIC), (foo,a)}

this corresponds to
<difference>
  <anyName/>
  <name>a</name>
</difference>


If canonicalize(NC) => PosSet< foo{Neg}<a> >, then possibleNames(NC)=>
{(foo,MAGIC),(foo,a)}

<difference>
  <nsName/>
  <name>a</name>
</difference>


If the notation is PosSet<...>, then NC doesn't accept (MAGIC,MAGIC). If
it's NegSet<...>, then NC accept (MAGIC,MAGIC).

If the notation contains foo{Pos}<...>, then NC doesn't accept
(foo,MAGIC). If it contains bar{Neg}<...>, then NC accepts (bar,MAGIC).


I think the only advantage of this algorithm (compared to yours) is that
it is guaranteed to be the smallest. But One can always minimize the
result of possibleNames easily.

--
Kohsuke KAWAGUCHI                          +1 650 786 0721
Sun Microsystems                   kohsuke.kawaguchi@eng.sun.com