[Bug 4598] Some compact expressions appear not to have normal forms

http://www.w3.org/Bugs/Public/show_bug.cgi?id=4598

           Summary: Some compact expressions appear not to have normal forms
           Product: WS-Policy
           Version: CR
          Platform: All
               URL: http://lists.w3.org/Archives/Public/public-ws-
                    policy/2007May/0297.html
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Framework
        AssignedTo: fsasaki@w3.org
        ReportedBy: dmh@tibco.com
         QAContact: public-ws-policy-qa@w3.org


Running through the basic case analysis, ignoring the outer <wsp:Policy>,
taking everything modulo commutativity and letting <Ai/> represent assertions
in normal form:


(1)
<ExactlyOne>
  <All>...</All>*
</ExactlyOne>

can be normalized if the <All> expressions can be normalized (or already
contain only assertions).  See below.

(2)
<ExactlyOne>
  <ExactlyOne>....</ExactlyOne>+
</ExactlyOne>

can be reduced by the associative rule.

(3)
<ExactlyOne>
  <ExactlyOne>...</ExactlyOne>*
  (<All>...</All>|<Ai/>)+
<ExactlyOne>

Does not appear to be in normal form, and there does not appear to be a rule by
which to reduce it.  Any ExactlyOne children may be reduced by associativity,
but this does not appear to help.

(4)
<All>
 <ExactlyOne>...</ExactlyOne>*
</All>

can be reduced by the distributive rule (or by the "empty" rule if there are no
children).

(5)
<All>
  <All>...</All>+
  <Ai/>*
</All>

can be reduced by the associative rule.

(6)

<All>
  <Ai/>*
</All>

is fine if it's a subexpression and can be wrapped in ExactlyOne if not.

(7)
<All>
 <ExactlyOne>...<ExactlyOne>+
 (<Ai/>|<All>...</All>)+
</All>

Does not appear to be in normal form, and there does not appear to be a rule by
which to reduce it.  Any All children may be reduced by associativity, but this
does not appear to help.

----

I see three possible resolutions:

1) I got the math wrong, and the forms that do not appear to have normal forms
actually do.  I'm pretty sure I got it right, and I've asked the list what
rules might apply, but on the other hand it seems unlikely that no one has
previously done this basic analysis.  If I missed something and there is a way
to normalize the expressions above, then we can close the issue.

2) Disallow expressions in forms (3) and (7), with a statement to the effect of
"The following compact forms have no normal form.  A processor MUST fault on
encountering them."

3a) Add a rule (say, "Promotion") to wrap bare assertion children in otherwise
non-normal expressions in the operator opposite their parent.

E.g., (note, these examples are of course non-normative; the text would be
normative)

<ExactlyOne>
  <A1/>
</ExactlyOne>

==> (promotion)

<ExactlyOne>
  <All>
    <A1/>
  </All>
</ExactlyOne>

----

<ExactlyOne>
  <All><A1/><A2/></All>
  <A3/>
</ExactlyOne>

==> (promotion)

<ExactlyOne>
  <All><A1/><A2/></All>
  <All><A3/></All>
</ExactlyOne>

----

<ExactlyOne>
  <All><A1/><A2/></All>
  <A3/>
  <ExactlyOne><A4/><A5/></ExactlyOne>
</ExactlyOne>

==> (associative)

<ExactlyOne>
  <All><A1/><A2/></All>
  <A3/>
  <A4/>
  <A5/>
</ExactlyOne>

==> (promotion)

<ExactlyOne>
  <All><A1/><A2/></All>
  <All><A3/></All>
  <All><A4/></All>
  <All><A5/></All>
</ExactlyOne>

3b) If that's not the right behavior, add some other rule or rules.

Received on Tuesday, 5 June 2007 20:27:36 UTC