UDC 519.95

CYBERNETICS AND CONTROL THEORY

G. A. AGASANDYAN

AUTOMATA WITH VARIABLE STRUCTURE

(Presented by Academician A. A. Dorodnitsyn, 12 VII 1966)

Problems of neurophysiology have led (beginning with W. McCulloch and W. Pitts) to the appearance of the mathematical theory of automata. One of the limitations of this theory is the condition that the transition functions of an automaton be invariant in time. It turns out that the representable events are those constructively specified by regular expressions. Many problems (including neurophysiological ones) confront us with automata whose transition functions are variable. The study of the possibilities arising from the resulting generalization of the concept “automaton” constitutes the content of this note. The method used goes back to D. Myhill (see (¹)).

An automaton with variable structure is a system
\(\mathfrak{A} = (X, S, M^n_{n-1}, s_0, F_n; n = 1, 2, \ldots)\), where \(X\) is a finite input alphabet; \(S\) is the finite set of states of the automaton; \(M^n_{n-1}\) is the transition function of the automaton, defined for every integer \(n \geqslant 1\) on the Cartesian product \(S \times X\) with values in \(S\); \(s_0\) is the initial state \((s_0 \in S)\); \(F_n\) is the set of marked states, also specified for all integers \(n \geqslant 1\). Let us note that, by virtue of the finiteness of the sets \(S\) and \(X\), the number of distinct functions in the sequence \(M^n_{n-1}\), as well as the number of distinct sets in the sequence \(F_n\), is always finite.

By \(P\) we denote the free semigroup generated by the letters of the alphabet \(X\). Each element \(p \in P\) is a word in the alphabet \(X\): \(p = x_1x_2 \ldots x_n\) \((x_i \in X,\ i = 1, 2, \ldots, n)\). The notation \(p_k^l = x_{k+1} \ldots x_l\) is introduced. In particular, \(p = x_1x_2 \ldots x_n = p_0^n\).

With the aid of the functions \(M^n_{n-1}\) one can naturally define functions \(M^m_n\) describing transitions from states at time \(n\) to states at time \(m\). They are specified by the recurrence relation

\[ M^m_n(s, p^m_n) = M^m_{n+1}\bigl[M^{n+1}_n(s, x_{n+1}), p^m_{n+1}\bigr]. \]

Here \(s \in S\) and \(p^m_n = x_{n+1} \ldots x_m\).

Sets of words from \(P\) are called events. An event \(U\) is called representable in the automaton \(\mathfrak{A}\) if it consists of those and only those \(p_0^n \in P,\ n = 1, 2, \ldots\), for which \(M^n_0(s_0, p_0^n) \in F_n\). Two automata with variable structure are called equivalent if the events they represent coincide. The class of all events representable in automata with variable structure will be denoted by \(\mathfrak{M}\).

From the point of view of representability of events in automata with variable structure, the question of a necessary and sufficient condition for representability of a given event is of interest. This question is solved as follows. Having fixed an event \(U\), we introduce, on the set of all words from \(P\), a relation of \(U\)-equivalence, denoted by \(\equiv_U\). For any pair of words \(p_0^n\) and \(q_0^m\) from \(P\), we say that \(p_0^n \equiv_U q_0^m\) if and only if \(n=m\) and, for any word \(r\) from \(P\), the assertion that both \(p_0^n r \in U\) and \(q_0^n r \in U\), and conversely, is valid.

Theorem 1. The relation of \(U\)-equivalence partitions the set of all words of length \(n\) into \(l_n\) classes, where the \(l_n\) are bounded in the aggregate \((l_n \leq l < \infty,\ n = 1, 2, \ldots)\), if and only if \(U \in \mathfrak{M}\).

The proof of the theorem at the same time contains a method for constructing an automaton representing the given event \(U \in \mathfrak M\). The states of this automaton are the classes of \(U\)-equivalence. The automaton constructed in this way is minimal, i.e., there is no automaton with variable structure representing the same event but with a number of states smaller than \(\max_n l_n\).

Using the formulated representability criterion one can establish that the class \(\mathfrak M\) of events representable by automata with variable structure is a Boolean algebra with respect to the operations of union and intersection of events and taking complements.

The following closure properties of the class \(\mathfrak M\) of representable events are of interest:

a) If \(U_1 \in \mathfrak M\), and \(U_2\) is a finite event, i.e., an event consisting of a finite number of words, then \(U_2U_1 \in \mathfrak M\) (\(U_2U_1\) is the product of the event \(U_2\) by the event \(U_1\), consisting of all words obtained by appending on the right to a word from \(U_2\) a word from \(U_1\)).

b) If \(U_1 \in \mathfrak M\), and \(U_2\) is a regular event, i.e., representable by finite automata, then \(U_1U_2 \in \mathfrak M\).

It is easy to see that the class \(\mathfrak M\) has the cardinality of the continuum. However, as will be seen from Example 3, it does not coincide with the set of all events.

The possibility of reducing an automaton with variable structure to ordinary finite automata is given by the following proposition.

Theorem 2. If an automaton with variable structure \(\mathfrak A=(X,S,M^n_{n-1},s_0,F_n;\ n=1,2,\ldots)\) generates the sequence \(\mathfrak a_n=(M^n_{n-1},F_n)\), \(n=1,2,\ldots\), which is periodic beginning with some \(n\), then the event representable in this automaton is regular.

Examples*.

1. The event \(U=\{0^{2^k-1},\ k=0,1,2,\ldots\}\) in the alphabet \(X=\{0,1\}\) belongs to \(\mathfrak M\). The minimal automaton representing this event contains three states \(s_1,\ s_2,\ s_3\); the transition function is given by the formulas \(M(s_1,0)=s_1,\ M(s_1,1)=s_2\), and in all other cases the function \(M\) takes the value \(s_3\). \(F_n=\{s_2\}\) for \(n=2^k,\ k=0,1,2,\ldots\), and \(F_n=\varnothing\) for \(n\ne 2^k,\ k=0,1,2,\ldots\). Let us note that the event \(U\) is not regular.

2. Let us introduce two events \(U_1=\{0^{2^k-1}1,\ k=0,1,2,\ldots\}\) and \(U_2=\{0^k1,\ k=0,1,2,\ldots\}\). Then the event \(U_1U_2\in\mathfrak M\), since \(U_2\) is regular (property b)). By means of Theorem 1 one constructs an automaton with only four states representing the event \(U_1U_2\).

3. The events \(U_1\) and \(U_2\) are the same as in Example 2. One can verify that \(U_2U_1\notin\mathfrak M\).

In conclusion, I consider it my pleasant duty to express gratitude to V. G. Sragovich for discussing the results presented.

Computing Center
Academy of Sciences of the USSR

Received
11 VII 1966

REFERENCES

1. M. O. Rabin, D. Scott, Cybernetics Collection, No. 4, IL, 1962; J. K. Shepherdson, ibid.

* \(0^n\) denotes a word consisting of \(n\) consecutive zeros.