Just as there is no loss of basic energy in the universe, so no thought or action is without its effects,

#### Idea Transcript

American Mathematical Society is collaborating with JSTOR to digitize, preserve and extend access to Proceedings of the American Mathematical Society.

http://www.jstor.org

LINEAR AUTOMATON TRANSFORMATIONS A. NERODE'

Let R be a nonempty set, let N consist of all non-negative rational integers, and denote by RN the set of all functions on N to R. If R is a ring, a map M: RNX-RN is linear if M(r,f,+r2f2) =r,(Mf,) +r2(Mf2) for ri, r2 in R, fi, f2 in RN. For a finite commutative ring with unit we determine which linear transformations M: RN--*RN can be realized by finite automata. More precisely, let A, B be finite nonempty sets. A map M: A N?BN is an automaton transformation if there exists a finite set Q, maps MQ: A XQ-*Q, MB: A XQ-*B, elements b in B, q in Q such that corresponding to each f in AN there exists an h in QN satisfying h(O) = ,

h(n + 1) = MQ(f(n), h(n)),

(Mf)(O)

=

(Mf) (n + 1) = MB(f(n), h(n)). (In automaton language, A is the input alphabet, B is the output alphabet, Q is the set of states, q is the initial state, b is the initial output, while MB(a, q) and MQ(a, q) are respectively the output and state resulting from input a and state q. For the case that A and B coincide with the set consisting of 0 and 1, the concept of automaton transformation is simply a variant of the concept of representable event of Kleene .) Call a matrix uij: NXN-?-R eventually doubly-periodic if for some positive integers Pi, P2, Pl, P2: (2) (3)

uj = u(i+pl)j for all i > Pi and all j, u1j = ui(j+P2) for all j > P2 and all i.

THEOREM 1. Let R be a finite commutative ring with unit. Then Al: RN-->RNis a linear automaton transformation if and only if there N-R such that: exists a matrix u,j: NXN( (i) for all j, u o;-; *.. (ii) for f in RN and n_O, (Mf)(n)=u.of(0)+u(n1)lf(1)+ +uonf(n); (iii) uij is eventually doubly-periodic.

n _ 1. A map Define r: RN--*RN by (rf) (0) = 0, (rf) (n) =f(n-1), M: RN -RN is translation invariant if for f in RN, Mrf =rMf. Call a sequence u0, ul,, .. eventually periodic if there exist positive integers Presented to the Society January 30, 1958; received by the editors December 26, 1957. 1 National Science Foundation postdoctoral fellow.

541

A. NERODE

542

P, p such that u, +=u.

for n>P;

[August

then p is a period.

Let R be a finite commutative ring with unit. Then a M: RN-*RN is linear translation invariant automaton transformation if and only if there exists an eventually periodic sequence uo0=, ul, * -*of elements of R such that for f in RN, (Mf) (n) = uof(n) + U21 +unf(0). COROLLARY.

Consider a linear difference equation (4) Si(n -1)F(n -1) + * * * + Sk(n- k)F(n -k) =G(n) + Ti(n - 1)G(n - 1) + * - * +T7(n

k)G(n -k),

-

where S1, * * * , Sk, T1, ** *, Tk, F, G are functions on the set of rational integers (positive and negative) to R which vanish for negative arguments. For fixed Si, . . . , Sk, T1, . . . , Tk, (4) induces a linear map M: RN--RN given by the requirement that whenever F, G jointly satisfy (4), and f is a member of RN such that f(n) = F(n) for n > 0, then (Mf) (n) =G(n) for n > 0. 2. Let R be a finite commutative ring with unit. Then RN-+RN M: is a linear automaton transformation if and only if induced by a linear differenceequation (4) with Si, Tk Sk, T1, ? eventually periodic for n 0. THEOREM

COROLLARY. Let R be a finite commutative ring with unit. Then M: RN---RN is a translation invariant linear automaton transformation if and only if induced by a linear difference equation (4) with S1, Sk, T1, * * * , Tk constant for n > 0.

We will need three lemmas to prove Theorems 1 and 2. LEMMA

1. Let R be a finite commutativering with unit. Endow R

with the discrete, RN with the product topology. Then L: RN-*R is linear and continuous if and only if there exists a finite sequence Wo, * * ' , Wm of elements of R such that for f in RN, Lf= Wof(O)+ + Wmf(m). PROOF.It is an easy consequence of the compactness of RN and the continuity of L that there exists an m such that Lf1= Lf2 whenever are in RN and agree for n?m. If we put ek(n)=I or 0 as n=k fi,f2 or not, then we may take Wk=L5k for k?m. Call M: AN--*BN causal if: for fi, f2 in AN, (Mfi)(0) = (Mf2) (0); for f', f2 in AN and k>0, if f1(n) =f2(n) for n
(Mf2)(k). Denote

by o(A) the set of finite sequences

(xo, * * * ,

xj)

consisting of elements from a finite set A. Call two such sequences

(xo,

543

LINEAR AUTOMATONTRANSFORMATIONS

1958]

*,

Xi), (yO, *

*,

Yk)

state-equivalent(relative to M) if for any

f in A , (Mfi) (n +j+ 1)

(Mf2) (n +k + 1) for all n > O, where fl, f2 are chosen satisfying: f1(n) = x. for 0< n j, f2(n) =y1. for 0?n
of Q. If X

=

(xo,

.

.

, xi)

is in v(A), define qx to be the h(j) determined from (1) by letting f(n) = x, for all n
Let

for

n=j. LEMMA 3. If S1, , Sk, T1, . . ., Tk are eventually periodic for n > 0, then (4) induces a linear automaton transformation. PROOF. We wish to apply Lemma 2; it suffices to show that M has only a finite number of intrinsic states, since any M induced by , k. Equation (4) is causal. Let pi, p,' be periods for Si, Ti, i =1, Then for ni sufficiently large, the intrinsic state of a finite sequence * * *, F(n-k), (xo, * * *, xn+l) is determined for n?ni by F(n-1), *, nmodpk,nmod *,G(n-k), n mod pi, G(n-1),* p', n mod pk'. Thus for n !!ni, finite sequences fall into at most z2kpl . .p8plt ... p I distinct intrinsic states, where z is the number of * elements of R. Thus AI has altogether only a finite number of intrinsic states. We now prove Theorems 1 and 2. If M is a linear automaton transformation, then for each n ? 0, the map Ln: RN---*R given by

544

A. NERODE

Lnf= (Mf) (n) is linear and continuous. Thus Lemma 1 applies and there exists a matrix Wnk: NXN-*R such that for each n _O we can find an m > 0 satisfying (Mf) (n) = Wnof(O)+ + Wnmf(m), for all f in RN. Causality implies Wnk = 0 for k > n. Setting uji = we need only verify (2) and (3) to satisfy Theorem 1. (5) Suppose that M: AN---*BN is an automaton transformation, and that f is a member of AN such that f(O), f(l), f(2), - * - is eventually periodic. Then (Mf) (0), (Mf) (1), (Mf) (2), - * - is eventually periodic. Moreover, if qn is the intrinsic state of (f(O), ,f(n)), then qo, ql, q2, * * -is eventually periodic. We employ (5) to prove (2) and (3). Since the kth column of uij consists of the entries 0, (Mbk)(k+ 1), (Mak)(k +2), (M&5k)(k +3), . it follows that this column is completely determined by the intrinsic state of a k-term sequence consisting of k -1 zero entries followed by a one. Since this sequence has the same intrinsic state as a k-term sequence consisting of zeros, (5) applies to show that this intrinsic state is an eventually periodic function of k, and hence proves (3). With this done, (2) is easy since it now suffices to show that the kth column is itself eventually periodic. But (5) applied to M8k yields this. Conversely, suppose that Ml is defined by a matrix uij satisfying (i), (ii), (iii) of Theorem 1. Define functions Ui by Uj(j) =uij for j_ 0, Uj(j) = 0 for j <0. Then the following linear difference equation induces M when recast in form (4). (In the notation of (2), put k =pi +Pi.) Ui(n

1)F(n

-

-

1) +

+ Uk(n

G(n)

-

G(n

-

k)F(n

-

1)

-U1(n-pi-1)F(n-pi=

-

k) Up,(n-k)F(n-k)

pi).

By (3), U1, *.. , Uk are eventually periodic for n>0; hence by Lemma 3, M is an automaton transformation. This proves both Theorem 1 and Theorem 2. REFERENCE 1. S. C. Kleene, Representation of events in nerve nets and finite automata, Auto-

mata Studies, Princeton University Press, 1956, pp. 3-41. INSTITUTE
{"ft_lang_label":"__label__en","ft_lang_prob":0.81617177,"math_prob":0.9961961,"size":8329,"snap":"2022-27-2022-33","text_gpt3_token_len":2626,"char_repetition_ratio":0.11915916,"word_repetition_ratio":0.057142857,"special_character_ratio":0.32092687,"punctuation_ratio":0.17518987,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9997009,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-07-05T00:01:41Z\",\"WARC-Record-ID\":\"<urn:uuid:4dfb7352-1359-4fcd-a1c8-75de0bff5736>\",\"Content-Length\":\"32126\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:c267c5ab-e9c0-418d-bbd4-b06bf06a2945>\",\"WARC-Concurrent-To\":\"<urn:uuid:a3297f6f-35c7-4f29-8186-98a995a20cbb>\",\"WARC-IP-Address\":\"104.21.6.122\",\"WARC-Target-URI\":\"https://pdffox.com/linear-automaton-transformations-pdf-free.html\",\"WARC-Payload-Digest\":\"sha1:X764SMH57Z2UP5O4VSXNUZBHVT255FTR\",\"WARC-Block-Digest\":\"sha1:N6EH77DIR3V6RBBCNCHY6Y4DS6HAYTQW\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-27/CC-MAIN-2022-27_segments_1656104506762.79_warc_CC-MAIN-20220704232527-20220705022527-00185.warc.gz\"}"}