2

When working with finite state machines, is there or can there be a well defined concept of 'before' and 'after'.

The ordering would, for example, tell me that one state is always considered to be 'before' another state, in the sense that any sequence of transitions through a state machine from some start state, to some end state, must always encounter a particular state before some other state.

I think these would be partial orders on the states of the machine. Sometimes two states would be neither before or after each other.

The particular problem I am trying to solve, is for field validations on items being passed through a workflow, defined as a state machine. If some field must be present in a particular state, it must also be present in states considered to come 'after' that state.

It is possible in the workflows, that items can be moved back into earlier states. For example, an item may go through a workflow and be 'published' but later un-published to be re-worked, and then put back through a workflow to be published again. There are edges in state machine that move forward towards end states, but also edges that move backwards towards start states. Given that, can I still define some sensible 'before' and 'after' relationships between states?

What I am trying to ask is, in state machine theory, is there a standard definition of what 'before' and 'after' mean that I can use to implement these functions?

|improve this question
  • 2
    I would think that you would have to identify certain transitions as back edges, when there are cycles in the states & transitions. This isn't normally done in state machines, afaik, but is commonly done in compiler technology (e.g. with graphs representing loops in code). This way, the normal flow can be distinguished from back edges, which gives a better ordering (e.g. to the code for optimization). – Erik Eidt Aug 10 '15 at 15:31
  • You can define a partial order like "state Y only happens after state X within less than n ticks", but not a total order. Imagine a FSM that contains a cycle. – 9000 Aug 10 '15 at 15:31
  • So what are your definitions of the 'before' and 'after' functions? – user2800708 Aug 11 '15 at 8:05
  • "state Y only happens after state X within less than n ticks". Why within less than n ticks? Why not just, state Y only happens after state X? – user2800708 Aug 11 '15 at 8:08
1

I don't think you can make definite assumptions for the general graph.

Some edges might bypass a Node, so it is not clear if the Node was visited or not. The state machine is like a map of possibilities.

Speaking of maps, you usually take the opportunities offered by a map one after the other. While the location itself has no notion of time, your visit of them certainly does.

Applying that to your state machine means that you create another graph that represents the ordered list of states visited and transitions used.

This graph (list) is never cyclic, even if the state machine is, because happening one after the other makes each visit of a Node (even those to the same Node) unique. This allows you to declare one Node to be before another one, if it is closer to the starting Node in the "visited states graph" than the other Node. "closer" means "it takes less transitions to get there"

|improve this answer
  • Yes, some nodes may be bypassed. That is ok though, suppose A -> B -> C, but also A -> C, where A is start, and C is accepting state. In this case, C comes after A, but C does not come after B, since I can get to C without going through B. – user2800708 Aug 11 '15 at 13:28
  • As I said, the 'before' and 'after' predicates are not total orders, but I expect them to be partial orders. I just want to know if standard definitions exist for them. – user2800708 Aug 11 '15 at 13:30
  • @user2800708 no, because if started at B, C comes after B. As I said, while it could be possible to define an order for special cases, this is not possible in general especially not if the graph is cyclic, so I don't see the point of your argument about a specific case. My answer covers all that nicely and produces a global order. Could you elaborate on what you do not like about my answer? – null Aug 11 '15 at 13:37
  • Your answer is that I should make a list of states visited in a particular sequence of transitions across the graph, using position in that list to decide if one is before/after another. What I want to know is for any legal sequence of transitions access the graph, can one state be considered to always come before/after another? Are such relations part of standard state machine theory? – user2800708 Aug 11 '15 at 13:52
  • Do you know what a 'partial order' is? – user2800708 Aug 11 '15 at 13:52
0

If you're interested in having different behaviour and/or tracking as part of the state whether a particular state has ever been visited, you can duplicate all of your possible states and then change all the transitions from the state of interest to the new duplicate of its original destination.

For example, consider the FSM with four states A, B, C and D, and the following transitions:

A -> B
B -> C
B -> D
C -> A

D is an end state

If we wanted to treat the result differently depending on whether or not C is visited we can change it to have 8 states, A..D and A'..D', with transitions:

A -> B
B -> C
B -> D
C -> A'
A' -> B'
B' -> C'
B' -> D'
C' -> A'

We can then say that A'..D' are after C, while A, B and D are before C.

|improve this answer
  • I hadn't considered the possibility of creating copies of states. But anyway, this doesn't help me, I just want to know if a pair of the original states can be considered to have one before/after the other or not. – user2800708 Aug 11 '15 at 13:27
  • I mean, we could re-write our workflow state machine to automatically create copies of states, where states are defined with multiple entry paths, such that those entry paths do not enforce the same rules. That could be useful, even if it just results in a warning to the user: "your state machine contains conflicting paths". – user2800708 Aug 11 '15 at 13:32
  • But, as above, I just want to know if state machine theory has standard definitions for 'before' and 'after' as partial orders on the states, and what those definitions are. Failing that, I will try and intuit my own definitions. – user2800708 Aug 11 '15 at 13:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.