W3C home > Mailing lists > Public > public-ws-policy@w3.org > June 2007

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

From: Asir Vedamuthu <asirveda@microsoft.com>
Date: Tue, 5 Jun 2007 19:17:20 -0700
To: David Hull <dmh@tibco.com>, "public-ws-policy@w3.org" <public-ws-policy@w3.org>
Message-ID: <C9BF0238EED3634BA1866AEF14C7A9E543155013B6@NA-EXMSG-C116.redmond.corp.microsoft.com>

Answers to your questions at http://lists.w3.org/Archives/Public/public-ws-policy/2007May/0297.html can be found at:

http://lists.w3.org/Archives/Public/public-ws-policy/2007Jun/0010.html
http://lists.w3.org/Archives/Public/public-ws-policy/2007Jun/0009.html

Regards,

Asir S Vedamuthu
Microsoft Corporation



-----Original Message-----
From: public-ws-policy-qa-request@w3.org [mailto:public-ws-policy-qa-request@w3.org] On Behalf Of bugzilla@wiggum.w3.org
Sent: Tuesday, June 05, 2007 1:27 PM
To: public-ws-policy-qa@w3.org
Subject: [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 Wednesday, 6 June 2007 02:17:50 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 8 January 2008 14:20:52 GMT