Re: SCXML: LCA bug ?

OK, I see the problem - the current definition of LCA treats the second transition as not exiting s12, which is not what we want.  We'll try to fix this for the next draft.  
  

-Jim

----- Original Message -----
From: Torbjörn Lager <lager@ling.gu.se>
To: Barnett, James
Cc: www-voice@w3.org <www-voice@w3.org>
Sent: Mon May 07 09:34:20 2007
Subject: Re: SCXML: LCA bug ?

Jim,

Sorry, I believe that I presented (what I see as) the problem in the 
wrong fashion - I wasn't clear enough. I do of course agree with what 
you are saying about the formal language theoretical stuff. The problem 
is that I suspect that a definition of LCA where (given the example) 
LCA(s11,s11)=s11 is not what you *want*. I think you *want* an LCA 
definition such that LCA(s11,s11)=s1. Consider an expanded version of 
our example:

   <state id="s1">
      <initial>
         <transition target="s11"/>
      </initial>
      <state id="s11">
         <transition event="e1" target="s12"/>
      </state>
      <state id="s12">
         <transition event="e2" target="s12"/>
      </state>
   </state >

The LCA is something that we need to compute when moving from one state 
to another, or from on state to itself. The problem is that with the 
current definition/algorithm, when moving from s11 to s12 the LCA = s1, 
but when moving from s12 to s12 it is s12. Why should they be different 
in those two cases? According to my intuitions they should not! What I 
am saying here is that I think the LCA should be s1 also when moving 
from s12 to s12.

Let me also say that I found this problem the hard way - struggling with 
an SCXML example that just didn't do the right thing. When I changed the 
algorithm the problem disappeared. Of course, it may be possible to keep 
the current definition of LCA and change the interpretation algorithm in 
other places. But why do that, when the proposed change is in fact more 
intuitive?

Regards,
Torbjörn

Barnett, James wrote:
> 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 13:59:33 UTC