State-space partition methods

This method has been used, among others, by Giles et al. (1992) . The $n_X$-dimensional state space hypercube is divided in $q^{n_X}$ equal hypercubes by dividing each of the edges of the state-space hypercube in $q$ equal parts. The hypercube containing the initial state ${\bf x}[0]$ of the DTRNN is labeled as the initial state of the FSM, $q_I$ and marked as visited. Then the DTRNN is alowed to process all possible input strings. If, after reading symbol $\sigma_k$ the DTRNN performs a transition from a state ${\bf x}[t-1]$ in a hypercube labeled as $q_j$ to a state ${\bf x}[t]$ in a new hypercube, then the new hypercube is given a new label $q_n$ (a new state is created) and the transition $\delta(q_j,\sigma_k)=q_n$ is recorded. If the transition results in a state ${\bf x}[t]$ in an existing hypercube $q_i$, the transition $\delta(q_j,\sigma_k)=q_i$ is recorded and the DTRNN dynamics on that string is no pursued no longer. The resulting FSM may then be minimized. The partition parameter $q$ is chosen to be the smallest one leading to a FSM which is compatible with the learning set.

A variation of this method was used by Blair and Pollack (1997) to study the nature of the representations achieved by DTRNN: instead of using the actual values of ${\bf x}[t]$ computed by the DTRNN, these authors used the centers of the hypercubes. The method of Blair and Pollack (1997) is used to determine whether the DTRNN actually shows a behavior that may be described in terms of a finite-state machine or a regular language; this is the only extraction method known that establishes (with desired accuracy) whether the DTRNN is behaving as a FSM or not before extracting a finite-state description of the behavior, thus addressing some of the concerns expressed by Kolen (1994).