# Re: SCXML: LCA bug ?

From: Torbjörn Lager <lager@ling.gu.se>
Date: Mon, 07 May 2007 15:34:20 +0200
To: "Barnett, James" <James.Barnett@aspect.com>

```
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:35:20 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:07:39 UTC