Re: Flattening of statecharts



Date view Thread view Subject view Author view Attachment view

From: Kinika Tasie-Amadi (kinika@yahoo.com)
Date: Thu 07 Aug 2003 - 17:46:37 BST


Hello Andrzej

For from always resulting in blow-up, flattening
hierarchical statecharts with *no orthogonality* will
always result in a statechart with *fewer* states.

In particular, if a hierarchical statechart has M
composite states and N simple states (i.e. M+N named
states), then a flattened version of that statechart
will have only N named states. For example, if a
statechart has two simplestates (StateA1 and StateA2)
that are both within a composite state (StateA),
instead of saying that the statechart is in StateA and
in StateA1, we can simply say that it is in StateA1.

What may blow up is the number of transitions between
states. For example, if there is a transition from
StateA above to some StateB, then in the flattened
statechart, this will be replaced by *two*
transitions: one from StateA1 to StateB and the other
from StateA2 to StateB.

Where you are likely to have blow-ups in terms of
states *and* transitions is of course, when
orthogonality is involved. For example, if StateC has
4 substates and StateD has 5 substates, and they are
composed orthogonally, then in the worst case, the
flattened version of the composition will have 4x5 or
20 states. It is the worst-case since simultaneous
transitions in both states (i.e. transitions
associated with the same trigger) can result in a
reduction in the number of flat states. Also, if a
transition in StateC depends on the current state in
StateD, then this will also reduce the blow-up.

In general, it is easy to describe a statechart that
cannot be flattened without blow-up. Infact, I can do
that right now. Assume a statechart whose top state is
the orthogonal composition of StateA and StateB.
Further, assume that StateA contains two substates
that are simplestates (StateA1 and StateA2) and StateB
contains three substates that are also simplestates
(StateB1, StateB2 and StateB3). Then, assume that
there is a transition from StateA1 to StateA2
triggered by x, that there is a transition from
StateB1 to StateB2 triggered by y, and a transition
from StateB2 to StateB3 triggered by z. If it helps,
assume that StateA1 is the default substate of StateA
and StateB1 is the default substate of StateB. I dare
say that no flattening algorithm can flatten this
statechart without blow-up.

Finally, I must add that what blows-up in the number
of states refers to a blow-up in the number of *named*
states. The number of unique states (or the number of
state configurations) remains the same after
flattening. For example, the orthogonal statechart
above has *five* named simplestates: StateA1, StateA2,
StateB1, StateB2 and StateB3. However, it exists in
one of *six* state configurations, that can be
described by: [StateA1,StateB1], [StateA1,StateB2],
[StateA1,StateB3], [StateA2,StateB1],
[StateA2,StateB2], [StateA2,StateB3] where for
example, [StateA1,StateB1] denotes that the statechart
is simultaneously in StateA1 and StateB1. The
flattened statechart will also exist in one of *six*
state configurations, possibly: [StateA1_StateB1],
[StateA1_StateB2], [StateA1_StateB3],
[StateA2_StateB1], [StateA2_StateB2],
[StateA2_StateB3] where for example, [StateA1_StateB1]
denotes that the flattened statechart is in state
StateA1_StateB1.

So, if the flattened statechart is intended for some
software tool, then probably, you can flatten with
impunity (in the example above, regardless of whether
the statechart includes hierarchy or is flattened, the
software tool will need to explore six state
configurations). However, if the flattened statechart
is intended for a human reader, then with reason, you
may be accused of trying to take the reader back to
the dark (headache-filled) ages.

Sincerely
Kinika

------------------
Kinika Tasie-Amadi
PhD Student
Dept of Computation
UMIST, England




 --- Andrzej Wasowski <andrzej_wasowski@yahoo.com>
wrote: > Dear pUML-ers,
> 
> Do you know of any published result that removing
> hierarchy from
> statecharts (not necesserily UML statecharts)
> incurres an exponential
> blow-up? [More precisely that regardless of
> flattening algorithm there
> will be always some hierarchical statecharts which
> cannot be flattened
> without the blow-up?]
> 
> I have found a few succintness results for
> statecharts in the
> literature, but not this precise one, which seems to
> be essential for
> numerous tools.
> 
> regards
> 
> andrzej
> 
> --
> Andrzej Wasowski, PhD student, IT University of
> Copenhagen
> http://www.mini.pw.edu.pl/~wasowski/
> 
> 
> 
>
________________________________________________________________________
> Want to chat instantly with your online friends? 
> Get the FREE Yahoo!
> Messenger http://uk.messenger.yahoo.com/
> 
> 
> 
> To remove yourself from this list please mail
> puml-list-request@cs.york.ac.uk
> with a message containing the word "unsubscribe".
>  

________________________________________________________________________
Want to chat instantly with your online friends?  Get the FREE Yahoo!
Messenger http://uk.messenger.yahoo.com/

Date view Thread view Subject view Author view Attachment view