Re: Flattening of statecharts

Date view Thread view Subject view Author view Attachment view

From: Andrzej Wasowski (
Date: Fri 08 Aug 2003 - 10:06:07 BST

Hi Kinika,

Thank you for your reply indeed. Apparently we misunderstood each
other. I will reply in details hoping that this will clarify my need
(as maybe someone else still knows the answer).

> Far from always resulting in blow-up, 

I did not say always. I said "it is always possible to find a
statechart which will blow-up during flattening".

> flattening
> hierarchical statecharts with *no orthogonality* will
> always result in a statechart with *fewer* states.

Unless you have a flattening algorithm which is "very bad". One can
always add irrelevant states. My question was not connected to any
flattening algorithm. I am interested to know if there is any published
result showing that use of hierarchy gives "inherent" saving.

> What may blow up is the number of transitions between
> states. 

I am generally interested in exposion of "model size", i.e. some
reasonable measure like number of states and number of transitions
times number of actions.

> Where you are likely to have blow-ups in terms of
> states *and* transitions is of course, when
> orthogonality is involved. 

yes but this result is not that interesting as it has been published
before (see paper by Harel&Drusinsky, "On the power of cooperative

> 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. 

This amounts to a well-known fact that the size of product automaton
explodes. I would not call this flattening though. By saying flattening
I mean removing hierarchy, while retaining concurrency. This leads to
a concurrent composition of kind-of Mealy&Moore-machines, or most
preferably just Mealy-machines.

> In general, it is easy to describe a statechart that
> cannot be flattened without blow-up. Infact, I can do
> that right now. [...] I dare
> say that no flattening algorithm can flatten this
> statechart without blow-up.

Firstly this statechart is already flat (in my definition of being
flat) and what you are trying to do is to make a product machine out of
it. Secondly I am not that much interested in description of flattening
algorithms or examples of specific statecharts. I was just asking if
anybody knows a good reference because I need this result for the paper
I am writing otherwise I will have to paste the proof in the paper
(less preferable).

People commonly refer to above mentioned paper of David Harel when
asked about it in the ocnversation. I have read the paper and according
to my understanding this paper does not presens any results related to
hierarchy, but only to cooperative concurrency.

> 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. 

If you mean the number of reachable states, then this is
"by-construction". Any transformation which would change it would
change the meaning of the model.

> 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 not all tools explore states and number of states to explore is
not the only factor you consider while building various tools.

> However, if the flattened statechart
> is intended for a human reader, 

No it is not :).

best regards


> Andrzej Wasowski, PhD student, IT University of
> Copenhagen

Want to chat instantly with your online friends?  Get the FREE Yahoo!

Date view Thread view Subject view Author view Attachment view