RE: SCXML: LCA bug ?

Torbjorn,
  The trick is that "ancestor-of" is a reflexive relationship, so LCA(s11, s11) = s11, because ancestor-of(s1, s1)= True.  

This is consistent with what I've seen in formal language theory text books - they distinguish between ancestor (or descendant) and proper-ancestor (and proper-descendant).  So s11 is an ancestor (and descendant) of itself, but not a proper ancestor or proper descendent of itself.  Though there is a problem in the draft: the function "isDescendent" should be called "isProperDescendant".  

I'll try to clarify the notation in the next draft.  

- Jim

-----Original Message-----
From: www-voice-request@w3.org [mailto:www-voice-request@w3.org] On Behalf Of Torbjörn Lager
Sent: Sunday, May 06, 2007 4:46 AM
To: www-voice@w3.org
Subject: SCXML: LCA bug ?


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 Monday, 7 May 2007 12:52:37 UTC