Forums

Transition and reaction difference in FSM?

Started by Davy December 24, 2006
Hi all,

I found there are transition and reaction in FSM/HSM. I only know there
is state transition in FSM. What's reaction mean? And what's there
difference?

BTW, I am studing Statecharts (or called Hierarchical State Machine,
i.e. HSM). Is it useful in software/hardware design?

Any suggestions are welcome!


Best regards,
Davy

In article <1167015961.917372.247050@f1g2000cwa.googlegroups.com>, Davy 
says...
> I found there are transition and reaction in FSM/HSM. I only know there > is state transition in FSM. What's reaction mean? And what's there > difference?
Not a terminology I'm familiar with. I'm more familiar with condition/action or event/action (and on entry/on exit/during actions).
> BTW, I am studing Statecharts (or called Hierarchical State Machine, > i.e. HSM). Is it useful in software/hardware design?
Definitely. Robert -- Posted via a free Usenet account from http://www.teranews.com
I agree with Robert Adsett, first there are useful, second the
terminology you use is 'strange'.

Where do you found "there are transition and reaction in FSM/HSM" ?
Perhaps a 'reaction' is a transition made in respons to an external
stimulus (a 'true' event) ?

Best regards

Sorry. I am familiar with FSM, but not familiar with its terminology.
We know that
transition is state transition. And do you mean reaction is the output
when state transition complete?

And I learned that there is "behavioral inheritance(i.e. same
transition in all sub-state of one super-state) " in statecharts/HSM.
Is it useful in practical system design?

Best regards,
Davy

bruno_pages wrote:
> I agree with Robert Adsett, first there are useful, second the > terminology you use is 'strange'. > > Where do you found "there are transition and reaction in FSM/HSM" ? > Perhaps a 'reaction' is a transition made in respons to an external > stimulus (a 'true' event) ? > > Best regards
Responding to Davy...

> I found there are transition and reaction in FSM/HSM. I only know there > is state transition in FSM. What's reaction mean? And what's there > difference?
Like the others, I don't know what 'reaction' means in the context of finite state machines. (I have never heard that term used in FSM context and I've been using FSMs for decades.) Could you provide the context for where the term was used?
> BTW, I am studing Statecharts (or called Hierarchical State Machine, > i.e. HSM). Is it useful in software/hardware design?
Actually, I think HSM means Harel State Machine; named after the inventor. (The dominant FSM models are: Mealy, Moore, and Harel.) While hierarchical structure of Harel FSMs is their most prominent feature, Harel FSMs also include history of past states or events. Harel FSMs are useful for describing very complex behavior in asynchronous environments in a single model. So they are commonly used for describing things like requirements for network protocol standards. However, that model complexity makes them difficult to construct and maintain. IME, one is better off with a simple Mealy FSM in procedural development or a Moore FSM in OO development. In fact, in an OO environment if one is tempted to use Harel for an object state machine it is almost always a sign that there was something wrong with problem space abstraction. IOW, in an OO environment one uses problem space abstraction to manage complexity by allocating complex behavior responsibilities across multiple peer objects using delegation. (AFAIK, the only OO methodology that advocates the use of Harel is ROOM.) ************* There is nothing wrong with me that could not be cured by a capful of Drano. H. S. Lahman hsl@pathfindermda.com Pathfinder Solutions http://www.pathfindermda.com blog: http://pathfinderpeople.blogs.com/hslahman "Model-Based Translation: The Next Step in Agile Development". Email info@pathfindermda.com for your copy. Pathfinder is hiring: http://www.pathfindermda.com/about_us/careers_pos3.php. (888)OOA-PATH
Hi Lahman,

I want to partition my large FSM to smaller ones. And I get some idea
from the statecharts.

In Harel's paper the HSM have four feature
1. Hierarchy: Simplify our thinking by partition large FSM into smaller
FSM parts
2. Orthogonality: the small FSM parts which are on the same layer and
from the same super-state should behave Orthogonality functionality (or
not similar functionality)
3. Broadcast: event from sub-state of one super-state trigger sub-state
of another super-state ???
4. History: re-enter the last state ???

I think feature 1 and 2 is very useful when you try to partition large
FSM. And I think feature 3 will cause complex implementation. So you
think so?

You said: "In fact, in an OO environment if one
> is tempted to use Harel for an object state machine it is almost always > a sign that there was something wrong with problem space abstraction."
But if you want a Hierarchy FSM or partition the FSM into small FSM parts, how can you do that without the idea from statecharts? BTW, about reaction, I find a Boost library about Statecharts which mention "reaction" http://boost-sandbox.sourceforge.net/libs/statechart/doc/tutorial.html Best regards, Davy H. S. Lahman wrote:
> Responding to Davy... > > > I found there are transition and reaction in FSM/HSM. I only know there > > is state transition in FSM. What's reaction mean? And what's there > > difference? > > Like the others, I don't know what 'reaction' means in the context of > finite state machines. (I have never heard that term used in FSM > context and I've been using FSMs for decades.) Could you provide the > context for where the term was used? > > > BTW, I am studing Statecharts (or called Hierarchical State Machine, > > i.e. HSM). Is it useful in software/hardware design? > > Actually, I think HSM means Harel State Machine; named after the > inventor. (The dominant FSM models are: Mealy, Moore, and Harel.) > While hierarchical structure of Harel FSMs is their most prominent > feature, Harel FSMs also include history of past states or events. > > Harel FSMs are useful for describing very complex behavior in > asynchronous environments in a single model. So they are commonly used > for describing things like requirements for network protocol standards. > However, that model complexity makes them difficult to construct and > maintain. > > IME, one is better off with a simple Mealy FSM in procedural development > or a Moore FSM in OO development. In fact, in an OO environment if one > is tempted to use Harel for an object state machine it is almost always > a sign that there was something wrong with problem space abstraction. > IOW, in an OO environment one uses problem space abstraction to manage > complexity by allocating complex behavior responsibilities across > multiple peer objects using delegation. (AFAIK, the only OO methodology > that advocates the use of Harel is ROOM.) > > > ************* > There is nothing wrong with me that could > not be cured by a capful of Drano. > > H. S. Lahman > hsl@pathfindermda.com > Pathfinder Solutions > http://www.pathfindermda.com > blog: http://pathfinderpeople.blogs.com/hslahman > "Model-Based Translation: The Next Step in Agile Development". Email > info@pathfindermda.com for your copy. > Pathfinder is hiring: > http://www.pathfindermda.com/about_us/careers_pos3.php. > (888)OOA-PATH
In article <1167045677.901397.146760@h40g2000cwb.googlegroups.com>, Davy 
says...
> Sorry. I am familiar with FSM, but not familiar with its terminology. > We know that > transition is state transition. And do you mean reaction is the output > when state transition complete?
First, this is a lot easier to follow if you don't top-post. Second, I believe what everyone has said so far is that they are not familiar with the term reaction in the context of state machines. Althoug I'm beginning to suspect it's a synonym for action.
> And I learned that there is "behavioral inheritance(i.e. same > transition in all sub-state of one super-state) " in statecharts/HSM. > Is it useful in practical system design?
Again a term I've not seen before, but if you mean defining a transition from a state such that that transition occurs regardless of the contained state then yes, it's a construct I use regularly. If you mean an on-entry, during or on-exit action that occurs in a state regardless of the contained state then again yes. Robert -- Posted via a free Usenet account from http://www.teranews.com
In article <CKSjh.7022$Rc5.6726@trnddc01>, H. S. Lahman says...
> Responding to Davy... > > > I found there are transition and reaction in FSM/HSM. I only know there > > is state transition in FSM. What's reaction mean? And what's there > > difference?
<snip>
> Actually, I think HSM means Harel State Machine; named after the > inventor. (The dominant FSM models are: Mealy, Moore, and Harel.) > While hierarchical structure of Harel FSMs is their most prominent > feature, Harel FSMs also include history of past states or events.
I think you're right.
> Harel FSMs are useful for describing very complex behavior in > asynchronous environments in a single model. So they are commonly used > for describing things like requirements for network protocol standards. > However, that model complexity makes them difficult to construct and > maintain.
I'll disagree here a bit. You may be right for some models, I can see building a statechart that was impossible to maintain and update. Having said that though I've used the Harel Statecharts to very good effect to simplify from what the state model would have been with a flat representation. The result was IMO also more maintainable and understandable mostly since it represented the desired behaviour with fewer transistion and/or states. Without automatic code generation from the statechart diagram I'm not sure that would have been the case though. Robert -- Posted via a free Usenet account from http://www.teranews.com
In article <1167096204.044434.222080@i12g2000cwa.googlegroups.com>, Davy 
says...
> BTW, about reaction, I find a Boost library about Statecharts which > mention "reaction" > http://boost-sandbox.sourceforge.net/libs/statechart/doc/tutorial.html
That makes reaction look like a synonym for action. Unfortuantely they never appear to actually define the term. Robert -- Posted via a free Usenet account from http://www.teranews.com
Responding to Davy...

> I want to partition my large FSM to smaller ones. And I get some idea > from the statecharts. > > In Harel's paper the HSM have four feature > 1. Hierarchy: Simplify our thinking by partition large FSM into smaller > FSM parts > 2. Orthogonality: the small FSM parts which are on the same layer and > from the same super-state should behave Orthogonality functionality (or > not similar functionality) > 3. Broadcast: event from sub-state of one super-state trigger sub-state > of another super-state ??? > 4. History: re-enter the last state ??? > > I think feature 1 and 2 is very useful when you try to partition large > FSM. And I think feature 3 will cause complex implementation. So you > think so?
I agree that 1 and 2 are a good idea. But if one is going to create independent peer FSMs (e.g., object state machines in an OO development), then they should /be/ independent. In Harel they are not because the protocol for their interactions are built into the superstate responsibilities. For example, one must provide rules for the broadcast in 3. That makes one large and complex state machine rather than multiple simple, independent state machines that interact asynchronously. BTW, without the hierarchy, one would usually design the peer FSMs somewhat differently than in the Harel perspective because the interaction protocols would likely be different. However, that just demonstrates that there is additional design structure needed in Harel to provide a single FSM. FWIW, I am not a fan of 4 at all because it seems to violate one of the fundamental rules of finite state automata on which FSMs are based. When processing the input alphabet a state should be context-independent; it should not know what the last state was or what the next state will be. [Note that is very important in an OO context because responsibilities are supposed to be intrinsic and self-contained.]
> > You said: "In fact, in an OO environment if one > >>is tempted to use Harel for an object state machine it is almost always >>a sign that there was something wrong with problem space abstraction." > > > But if you want a Hierarchy FSM or partition the FSM into small FSM > parts, how can you do that without the idea from statecharts?
I submit that one wants to decompose complex state machines into simpler ones, but one does not need a hierarchical structure to do that. Once the simpler, independent state machines are defined they can talk to each other by sending events. Occasionally the Harel model will be more elegant (i.e., fewer states and transitions in total) but one pays for that in getting it to work properly, testing it, and modifying it when requirements change. [Caveat. There is a common use of superstates as a /notational/ artifact to reduce transition clutter in Statecharts: +-----------------------------------+ | Error ^ | | | | | +------------+ | E1 | | | State1 | | | | | | | +------------+ | | | ^ | | | E2 | E3 | | | | | | V | | | +------------+ | | | State2 |<----- | | | | E4 | | +------------+ | | | +-----------------------------------+ In this case there can be a transition to the Error state from either State1 or State2 and one always transitions from Error to State2. However, this isn't a true Harel because all the events are external (not internally broadcast) and all the states are actually peers. That is, one could draw it as: +-----------------+ | Error |-------+ | | | +-----------------+ | E4 ^ ^ | | E1 | E1 | | | V +-----------+ +--------------+ | State1 | E2 | State2 | | |--------->| | | | | | | |<---------| | | | E3 | | | | | | +-----------+ +--------------+ IOW, the superstate is simply saving the clutter of multiple E1 transitions. (Which isn't important here but could be if there were a half dozen states from which one transitions to Error.)
> > BTW, about reaction, I find a Boost library about Statecharts which > mention "reaction" > http://boost-sandbox.sourceforge.net/libs/statechart/doc/tutorial.html
The reference still doesn't define what it means. However, from the usage I would guess that they are talking about a Mealy FSM model where actions are associated with transitions rather than states. In that case one when there are multiple transitions into a state, one could have different actions execute depending on which transition was actually triggered to get to the state. Then "reaction" would simply be a synonym for the more common notion (at least in OO circles) of a response. ************* There is nothing wrong with me that could not be cured by a capful of Drano. H. S. Lahman hsl@pathfindermda.com Pathfinder Solutions http://www.pathfindermda.com blog: http://pathfinderpeople.blogs.com/hslahman "Model-Based Translation: The Next Step in Agile Development". Email info@pathfindermda.com for your copy. Pathfinder is hiring: http://www.pathfindermda.com/about_us/careers_pos3.php. (888)OOA-PATH