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/