State transition graphs

The grammars for regular languages can be conveniently specified by finite state transition graphs for the finite automata that recognize them. The vertices of the graph represent the the system states Cj E and the arcs represent the possible input states Uj A. The arrows point to the next state that will result from the initial state when the input on the arc is applied. 

The state transition graph for this example is given in figure 2.5. 

Although CA are most often assumed to live 011 infinitely large lattices, we can equally well consider lattices that are finite in extent (which is done in practice regardless, since all CA simulations are ultimately restricted by a finite computer memory). If a lattice has N sites, there are clearly a finite number,, of possible global configurations. The global dynamical evolution can then be represented by a finite state transition graph Gc, much like the one considered in the description of an abstract automaton in section 2.1.4. 

Fig. 2.9 The state transition graph Gc, computed for a Tdim lattice consisting of iV = 4 points (with periodic boundary conditions), and totalistic rule T2 . The vertices labeled ti represent transient configurations those labeled cd represent cyclic states, and give rise to the formal cycle cum decomposition C[ j =[3, lj-f[2,2].

Figures 3.38 and 3.39 show typical space-time patterns generated by a few r = 1 reversible rules starting from both simple and disordered initial states. Although analogs of the four generic classes of behavior may be discerned, there are important dynamical differences. The most important difference being the absence of attractors, since there can never be a merging of trajectories in a reversible system for finite lattices this means that the state transition graph must consist exclusively of cyclic states. We make a few general observations.

What does the set of possible state transition graph topologies for families of structurally similar graphs look like ... 

Because S ggj (t) is determined by considering all possible evolutions on a finite lattice, it must obviously be related to certain properties of the global state-transition graph, G. For example, at large times, 5 get(t —> oo) is given by the fraction of states that are on cycles in G. 

As suggested at the beginning of tiiis subsection, we can by reversing the above reasoning process - partially infer the topological structure of the global state transition graph, Qc-... 

The following lemma shows that the tree structure of the state transition graph Q is very regular. Notice, in particular, that since the proof makes no assumption on the form of T, the result is generally valid for ail additive rules. 

The much more difficult task of finding how often a given state transition graph appears when one samples all possible topologies (or how the Q sets are individually weighted), remains an open question. 

Table 5.2 Number of topologically distinct connected graphs ) ), number of cyclic equivalence classes Q, maximal numbers of possible cycle sets Cot and Ct for OT and T rules, respectively, and the maximal number of possible distinct topologies of the state transition graph, calculated for graphs with size fV=5,6,..., 12 in T 2. ...

Fig. 6.1 Finite State Transition graph (STG) for the regular language C = jol" ...

Fig. 6.2 Finite state transition graph for the CA rule defined in equation 6.8 see text.

Table 6.2 Number of nodes Ht, C = 0,.. . 4 in the minimal deterministic state transition graph (DSTG) representing the regular language r2t[0, where 0 is an elementary fc = 2, r = 1 CA rule Amax is the maximal eigenvalue of the adjacency matrix for the minimal DSTG and determines the entropy of the limit set in the infinite time limit (see text), Values are taken from Table 1 in [wolf84a. ...

In the context of CA systems, it turns out that there is a difference between rules that are invertible and rules that are time-reversal invariant. A global CA rule S —> S, mapping a global state ct S to some other global state ct S, is said to be invertible if for all states ct S there exists exactly one predecessor state O S such that (cr) = a. The state transition graphs G for all such rules must therefore consist entirely of cycles. 

Consider an order W system and a random function 4> which maps each of the H = 2 possible binary states Si to unique successor states Sj = cyclic structure of the corresponding state transition graph... 

The main objective of the study is the abUily to analyze an identified model in identifying automaton models from observations. We want to take an established method to learn a DFA and apply it to our timed sequences. Our problem could be modelled as a timed-state transition graph, a probabilistic deterministic finite automaton (PDFA) taking into account timed-event. We also have a set of positive timed-strings (or time-stamped event sequences). 

Preliminary Mapping of the Set of Strings. The objective is to obtain a stochastic state transition graph taking into account the length-of-stay in each state. So we have to associate for each occurrence of a symbol (event) in order to model time value. In practice, we use the evaluation date. 

To obtain stochastic state transition graph taking into account the lengh-of-stay in each state (5 to 1). 

CU programs are usually expressed as state transition graphs (STGs). In many CU programs, it is possible to find subsequences that occur in several places in the STG. Two sequences are identical if and only if they produce the same output sequences for all possible input sequences. The basic idea of a range of different architectures is to re-use these state sequences so that only one copy is needed in the implementation, thereby reducing the area of the CU. 

High-level synthesis adds the design structure to the SSIM. Scheduling consists basically in control synthesis and adds a control finite state machine (FSM) to the SSIM. The synthesized FSM is represented by its state transition graph. Allocation consists basically in data-path synthesis and adds a data path to the SSIM. The synthesized data-path is also represented as a graph (netlist). 

Figure 6 shows the BFSM specificatim for the dequeue machine. This BFSM requires both a state transition graph and a list of cmistraints that the input/output events must obey. When the machine perfmns a read or write on the extonal RAM, for example, it must wait one cycle fix>m the time the address is presented... 

---