Representing state transitions

A method for representing state transitions within a state machine includes representing a set of allowed transitions between states as a transition pair wherein a first value of the transition pair indicates a set of nodes from which to transition and a second value of the pair indicates a set of nodes to which to transition. The nodes represent states within a state machine. The method further includes defining a role of an entity within the state machine by assigning a number of transition pairs to the entity, the value pairs defining how the entity can transition through the state machine.

BACKGROUND

Aspects of the present invention relate in general to state machines, and more particularly, to methods for representing transitions between states within those state machines. A state machine is a model that can describe a variety of human or computer processes. The state machine defines several states in which the process may exist. The transitions between states may involve both conditions and actions. The conditions define what has to be in order to cause a transition between states. Actions define what takes place during the transition. For example, a state machine may model a door that is in either an open state or a closed state. While the door is in a closed state, conditions for a transition to an open state may be a turn of the doorknob and a force placed against the door. The actions involved in the transition to an open state involve the actual movement of the door.

State machines are often used to model complex processes. These processes may involve human processes, machine processes, or a combination of both. Various computer applications may be used to develop and represent such complex state machines. These state machines may be represented graphically to a user. In general, nodes are used to represent states while vertices between those nodes represent conditions and actions associated with a transition between states. One limitation of such state machines is that they only allow for specifically defined transitions between particular states. In some cases, it may be desirable to define transitions from each state to every other state within the state machine. This may especially be the case for state machines that model human processes. However, it can be time consuming and cumbersome for a developer of the state machine to define each transition between every state.

BRIEF SUMMARY

A method for representing state transitions within a state machine includes, with a physical computing system, representing a set of allowed transitions between states as a transition pair wherein a first value of the transition pair indicates a set of nodes from which to transition and a second value of the pair indicates a set of nodes to which to transition, the nodes representing states within a state machine, and with the physical computing system, defining a role of an entity within the state machine by assigning a number of transition pairs to the entity, the transition pairs defining how the entity can transition through the state machine.

A computing system includes a processor and a memory communicatively coupled to the processor. The processor is configured to represent a set of allowed transitions between states as a transition pair wherein a first value of the transition pair indicates a set of nodes from which to transition and a second value of the pair indicates a set of nodes to which to transition, the nodes representing states within a state machine and define a role of an entity within the state machine by assigning a number of transition pairs to the entity, the transition pairs defining how the entity can transition through the state machine.

A computer program product for representing transitions between states in a state machine includes a computer readable storage medium having computer readable code embodied therewith, the computer readable program code includes computer readable program code configured to represent a set of allowed transitions between states as a transition pair wherein a first value of the transition pair indicates a set of nodes from which to transition and a second value of the pair indicates a set of nodes to which to transition, the nodes representing states within a state machine and computer readable program code configured to define a role of an entity within the state machine by assigning a number of transition pairs to the entity, the transition pairs defining how the entity can transition through the state machine.

DETAILED DESCRIPTION

As mentioned above, one limitation of such state machines is that they only allow for specifically defined transitions between particular states. In some cases, it may be desirable to define transitions from each state to every other state within the state machine. This may especially be the case for state machines that model human processes. However, it can be time consuming and cumbersome for a developer of the state machine to define each transition between every state.

In light of this and other issues, the present specification discloses methods and systems for efficiently representing transitions between states within a state machine. Such representations will simplify the task of developing such models when using state machine modeling applications. Such representations also allow for easily defining the roles of entities involved in the process that is modeled by the state machine.

According to certain illustrative examples, a transition within a state machine can be represented by a transition pair. The transition pair includes a first value and a second value. The first value describes a node or set of nodes from which a transition can be made. The second value describes a node or set of nodes to which a transition can be made. For example, the transition pair {1, [2, 3, 4]} indicates that from node1, a transition can be made to either node2, node3, or node4. In some cases, various identifiers can be used to indicate all states or particular subset of states. For example, the transition pair {*, 1} indicates that a transition can be made from any node back to node1. In a further example, the transition pair {*, *} indicates that a transition can be made from any state to any other state.

By representing transitions in such a manner, a user can easily define transitions within a state machine modeling application. Specifically, the user does not have to individually define each transition. Furthermore, by simply representing transitions as transition pairs, a state machine developer can assign roles to entities which may navigate the state machine. For example, a state machine may model a particular business operation. Various human roles are typically involved in such business operations. A supervisor may be able to transition the process between states differently than a worker. Thus, different entities may be assigned roles using the above described manner of representing transitions. For example, a particular type of worker may be assigned a role using the expression: role A={1, [1,3,4,7]}. In a further example, a manager may be assigned a role using the expression: role M={*,*}. Defining transitions and roles in such a manner provides an efficient manner of representation.

Referring now to the figures,FIG. 1is a diagram showing an illustrative physical computing system (100) that can be used for state machine development. According to certain illustrative examples, the physical computing system (100) includes a memory (102) having software (104) and data (106) stored thereon. The physical computing system (100) also includes a processor (108) and a user interface (110).

There are many types of memory available. Some types of memory, such as solid state drives, are designed for storage. These types of memory typically have large storage volume but relatively slow performance. Other types of memory, such as those used for Random Access Memory (RAM), are optimized for speed and are often referred to as “working memory.” The various forms of memory may store information in the form of software (104) and data (106).

The physical computing system (100) also includes a processor (108) for executing the software (104) and using or updating the data (106) stored in memory (102). The software (104) may include an operating system. An operating system allows other applications to interact properly with the hardware of the physical computing system. Such other applications may include those which are designed to develop state machine models.

A user interface (110) may provide a means for the user (112) to interact with the physical computing system (100). The user interface may include any collection of devices for interfacing with a human user (112). For example, the user interface (110) may include an input device such as a keyboard or mouse and an output device such as a monitor.

FIG. 2Ais a diagram showing an illustrative general state machine model (200). As mentioned above, a state machine is often represented by a number of nodes. These nodes represent the various states in which the state machine may exist. The vertices connecting the nodes define the transitions between the states. A transition between states involves both pre-conditions and actions. The pre-conditions define what has to happen to cause the transition and the actions define what happens during the transition to bring the state machine to the next state.

In the example shown inFIG. 2A, State1(202-1) can be defined as an initial state. From this initial state, the state machine can transition to either State2(202-2), State4(202-4) or state5(202-5). From State2(202-2), the state machine can transition to State3(202-3) and from there back to State1(202-1). From State4(202-4), the state machine can transition to State5(202-5) and from there back to state1(202-1).

FIG. 2Bis a diagram showing an illustrative state machine model wherein each state can transition to any other state. As mentioned above, in some cases, state machines model human workflows. Thus, more flexibility is often desired. Thus, it is sometimes preferred to allow mechanisms for the state machine to transition from any state to any other state. As can be seen fromFIG. 2B, this produces an excessive amount of vertices. This can be especially cumbersome for large and complex state machines involving hundreds or thousands of states.

FIG. 3is a diagram showing an illustrative example of a state machine model. According to one example, a state machine model may be used to model the operation of a vending machine. The following example is simply to illustrate a process that may be modeled with a state machine.

In its default state, the vending machine may be in a ready state (302). In response to various human based actions, the vending machine may transition to a different state. For example, if a human user puts in a certain amount of money, then the vending machine will transition to state2. In this state, the vending machine is awaiting a selection from the user as to which item he or she desires to purchase. If the user puts a different amount of money into the vending machine, then the state machine transitions to state3(306) to await a selection from the user from group B. Thus, the pre-conditions for causing the transition between states are a human user putting money into the vending machine. The actions made during the transitions are the execution of whatever hardware and software systems within the vending machine are used to await a particular selection from the user.

While in either state2(304) or State3(306) the state machine waits for a response from the user as to which selection from the appropriate group he or she chooses. In response to such user input, the state machine will transition to State5(310), State6(312), or State7(314). During these states, the vending machine is dispensing the selected item. Upon completion of dispensing the item, the state machine will transition back to the default ready state, State1(302). Thus, the pre-conditions for transitioning back to the initial state are completion of the dispensing process.

The state machine may also include a maintenance state (308) wherein an operator of the vending machine has the ability to initiate this state for various maintenance or restocking purposes. The pre-conditions for transitioning to such a state may include a test for determining that the person attempting to enter maintenance mode is authorized to do so.

As mentioned above, one issue with using state machines to model complex processes is that each transition allowed has to be carefully defined. In some cases, it is desirable that a state machine have some mechanism for forcing a transition between states where there is not normally a process related transition. Representing possible transitions from every state to every other state can be very difficult. When represented graphically, the vertices between nodes can become too numerous to distinguish. When represented as a list associated with each node, the lists become quite large. These issues increase as the size and complexity of the state machine increases. In light of this issue, the present specification discloses a method for efficiently representing allowed transitions between states within a state machine.

FIG. 4Ais a diagram showing an illustrative transition pair (400). According to certain illustrative examples, the transition pair (400) includes a first value (404) and a second value (406). In one example, the first value (404) and second value (406) are placed within brackets and separated by a comma. However, other methods of notation may be used to express the transition pair. The first value (404) defines either a single node or a set of nodes from which the state machine is able to transition. The second value (406) defines either a single node or a set of nodes to which the nodes indicated in the first value (404) can transition.

FIG. 4Bis a diagram showing an illustrative table of transition pairs. The transition pair in row1defines both the first value (404) and the second value (406) as a single node. Thus, this transition pair indicates that the state machine is able to transition from node1to node4. The transition pair in row2defines the first value as a single node and the second value (406) as a set of nodes. This transition pair thus indicates that the state machine can transition from node1to either node2,3, or4. The transition pair in row3defines the first value as a set of nodes and the second value (406) as a single node. This transition pair thus indicates that the state machine can transfer from either node2,5, or6to node3.

In some cases, various indicators may be used in place of a node or set of nodes to indicate a previously defined set of nodes. For example, the * character may be used to indicate all nodes within the state machine. Thus, the transition pair in row4indicates that any node within the state machine can transition back to node1. In another example, the developer of the state machine may create predefined sets. In this example, the predefined set is labeled with a letter inside of parentheses. Thus, the transition pair in row5indicates that from any of the nodes within predefined set B, the state machine can transition to any node.

FIG. 5is a diagram showing an illustrative state transition matrix. In addition to representing transitions through use of the transition pairs described above, some transitions maybe represented through matrices. According to certain illustrative examples, a state transition matrix includes a number of rows and a number of columns. The rows represent nodes from which the state machine may transition and the columns represent nodes to which the state machine may transition. The cells (506) within the state transition matrix define whether or not a transition is allowed from the row of that cell to the column of that cell. For example, a transition is allowed from node1to node3because there is a ‘1’ in row1, column3. Conversely, there is no transition allowed between node5and node2because there is a ‘0’ in row5, column2.

FIG. 6is a diagram of a table (600) showing illustrative assignment of roles to entities associated with a state machine model. By having an efficient method of representing state transitions within a state machine, roles can be assigned to entities using this method of representing transitions. For example, different entities may navigate through the state machine in different manners. Typically, defining how an entity may navigate a state machine involves conditions defined for each state transition. For example, the developer would have to explicitly state, for each transition, which entities can and cannot use that transition. However, by efficiently representing state transitions as defined above, user roles can be defined in a single expression.

According to certain illustrative examples, the table (600) includes a role column (602) and an assignment column (604). The role column defines specific roles which may be assigned to different entities. For example, using the vending machine example above, a customer may have a different role for navigating the state machine model than an operator of the vending machine. Specifically, the operator may have the ability to transition to the maintenance state. Additionally, the operator may be able to jump to any state without having to abide by certain conditions which the customer may have to abide by in order to transition to different states.

In one example, a role can be assigned using an expression such as role A={1, [2, 5]} AND {2, *}. Thus, the manner in which an entity having role A can transition through the state machine is defined by those transition pairs. Specifically, an entity with role A can transition from state1to both state2and5. Additionally, that entity with role A may transition from state2to any state within the state machine.

In some cases, the assignment of the role of an entity may be defined, at least in part, by a state transition matrix. For example, role B={*, 1} AND [F]. Thus an entity with role B can transition from any state back to state1and may transition in any manner defined by state transition matrix F. In some cases, an entity may be given a universal role that allows that entity to transition from any state to any other state as defined by role D.

FIG. 7is a diagram showing an illustrative graphical user interface for an application used to develop state machine models. According to certain illustrative examples, the user interface (700) may be embodied in the form of a window (702). The user interface (700) may include a toolbar (704) and a graphical mode (708). The user interface may also include a new node control (710), an edit node control (712), a transition pairs control (714), a transition matrices control (716), and a roles control (718). The graphical user interface illustrated and described herein is a simple example of an interface and is not intended to limit the manner in which a graphical user interface embodying principles described herein should look or operate.

The toolbar includes the various options and tools that the developer may use to create a state machine model. The state machine graphical model (708) may display the current state machine or portion of that state machine to the developer. The various controls on the left side of the graphical user interface (700) provide various features to be used in the creation and development of a state machine.

The new node control (710) can be used to create a new node. With the creation of a new node, the developer can define a new state in which the state machine may exist. The developer can define the characteristics of theses states and what conditions and actions are associated with transitioning to and from them. The developer may edit these nodes using the edit node control (712).

The transition pairs control (714) allows the developer to enter in the expressions that represent transitions that are allowed within the state machine. The user may create new transition pairs and edit those pairs which have already been created. Although the transition pairs define which transitions are allowed, they do not define the conditions and actions associated with those transitions. If the developer wishes to define such conditions and actions, then he or she can proceed through each transition and do so. However, the developer can still be provided with an efficient representation of the allowed transitions through the transition pair expressions. The developer may also define state transition matrices using the transition matrices control (716).

The roles control (718) may allow the developer to assign roles to various entities associated with the state machine. The term “entity” when referring to those associated with a state machine refers to the type of persons or machine systems that may be involved in the state machine. For example, when referring to a business process, the entities may include managers of varying levels, and workers with different privileges. Each of these entities may be assigned roles using the expressions described above. These roles will define how those entities may navigate the state machine.

FIG. 8is a flowchart showing an illustrative method for representing state transitions. According to certain illustrative examples, the method includes, with a physical computing system, representing a set of allowed transitions between states as a transition pair wherein a first value of the transition pair indicates a set of nodes from which to transition and a second value of the pair indicates a set of nodes to which to transition, the nodes representing states within a state machine, and with the physical computing system, defining a role of an entity within the state machine by assigning a number of transition pairs to the entity, the transition pairs defining how the entity can transition through the state machine.