W3C home > Mailing lists > Public > www-voice@w3.org > April to June 2007

SCXML: LCA bug ?

From: Torbjörn Lager <torbjorn.lager@gmail.com>
Date: Sun, 6 May 2007 10:46:18 +0200
Message-ID: <6ad4bdae0705060146w57108168w3df69fbbef744ca2@mail.gmail.com>
To: www-voice@w3.org

I think the draft needs a clearer definition (and not just an
algorithm) of "least common ancestor" (LCA), together with a few clear
examples of the tricky bordering cases.

Here's what has been bugging me for a while. In my own understanding, given

 <state id="s1">
    <state id="s11">
    <state id="s12">
 </state>

the following should hold

 1)  LCA(s11,s12) = s1
 2)  LCA(s11,s11) = s1
 3)  LCA(s1,s11)  = s1

However, the algorithm in the draft:

 state findLeastCommonAncestor(state1, state2) {
   if (isDescendent(state2, state1)) {
     return state1;
   } elsif(isDescendent(state1, state2)) {
     return state2;
   } elsif (state1 == state2) {
     return state1;
   } else
       for anc in listAncestors(state1, SCXML) {
         if (isDescendant(state2, anc)){
            return anc;}
      }//end for
   //end else
 }

doesn't get 2) right, since findLeastCommonAncestor(s11,s11) = s11,
which I believe is wrong. I propose that

   } elsif (state1 == state2) {
     return state1;

be changed into

   } elsif (state1 == state2) {
     return getParent(state1);


Best regards,
Torbjörn
Received on Sunday, 6 May 2007 08:46:22 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Sunday, 6 May 2007 08:46:24 GMT