An Algorithmic state machine (ASM) is a directed connected graph containing an initial vertex (Begin), a final vertex (End) and a finite set of operator and conditional vertices (Fig. 1). The final, operator and conditional vertices have only one input, the initial vertex has no input. Initial and operator vertices have only one output, a conditional vertex has two outputs marked by "1" and "0". A final vertex has no outputs.

Figure 1. Vertices of Algorithmic state machine

In ASM, a logical condition is written in each conditional vertex. It is possible to write the same logical condition in different conditional vertices. A microinstruction (an operator), containing one, two, three or more microoperations, is written in each operator vertex of ASM. It is possible to write the same operator in different operator vertices.

ASM vertices are connected in such a way that:

  • Inputs and outputs of the vertices are connected by arcs directed from the output to the input, each output is connected to only one input;
  • Each input is connected to at least one output;
  • Each vertex is located on at least one of the paths from vertex Begin to vertex End.
  • One of the outputs of a conditional vertex can be connected to its input. We will call such conditional vertices the “waiting vertices”, since they simulate the waiting process in the system behavior description.

As the first example, let us consider a rather smart Traffic Light Controller (TLC) presented in the flowchart in Fig. 2. First of all, we want to warn you. This ACM is quite complex, but after considering the ACM transformations you will see that it is very easy to build it. Moreover, at this stage it is not important to understand how does it works.

Figure 2. A Traffic light controller

Nevertheless, we will shortly describe its behavior. This controller is at the intersection of a main road and a secondary road. TLC have different day and night programs. Day program (Bit0=0) has two modes. when prog=1, cars can move along the main road during t_main time. In the second mode (prog=1) car move via the main road until the sensor sec_ full tells to TLS that second road is full.

On the night (Bit0=1), the traffic on the main road doesn't stop until a pedestrian appears on the main road (pd_main=1) or the number of cars on the second road reach the number written in the register rg_sec_car.

The traffic on the second road is the same for the day and the night programs. Cars move on the second road during time written in rg_t_sec. The switching between traffic on the main and the second roads takes time written in the register rg_t_int.

Our smart controller can recognize an ambulance on the road. When an ambulance is on the road, the signal amb is equal to one (amb = 1), when there is no ambulance on the road this signal is equal to zero (amb = 0). When the ambulance is on the road, outputs of conditional vertices with logical condition amb marked by ΄1΄, bring us to the intermediate state to let cars to finish their driving: main_yel:=1; sec_yel := 1; t := 0. One more logical condition dmain tells us where the ambulance is – whether it is on the main road or on the second one. If it is on the main road (dmain=0), after time written in intermediate register reg_t_int, the traffic light will be green on the main road, otherwise (dmain=1) the traffic light will be green on the second road.

Sometimes we use ASM in which logical conditions and microoperations are replaced by x1, x2, … and y1, y2, … and their operators are replaced by operators Y1, Y2, … . Such ASM for ASM in Fig. 2 is shown in Fig. 3.

Figure 3. The same ASM with replaced operators and logical conditions