From: Andrzej Wasowski (andrzej_wasowski@yahoo.com)
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 concurrency"). > 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 -- > 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/