[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]

*Subject*: **canonical representation of NC.**

*From*:**Kohsuke KAWAGUCHI <kohsuke.kawaguchi@eng.sun.com>***To*: TREX ML <trex@lists.oasis-open.org>*Date*: Sat, 05 May 2001 12:03:16 -0700

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

**Follow-Ups**:**More thoughts on canonical representation / NC equivalence***From:*Kohsuke KAWAGUCHI <kohsuke.kawaguchi@eng.sun.com>

**References**:**Re: Guarded normal form (part 1)***From:*Kohsuke KAWAGUCHI <kohsuke.kawaguchi@eng.sun.com>

**Re: Guarded normal form (part 1)***From:*James Clark <jjc@jclark.com>

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]

Powered by eList eXpress LLC