[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Subject: Re: Guarded normal form (part 1)
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
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Powered by eList eXpress LLC