The crucial discovery reported here is that the free monoid U* on the input set U does not yield a sufficiently rich set of inputs when algebraic structure is placed on the machine. For group machines, the appropriate structure is the coproduct U~ of an infinite sequence of copies of U. U~ reduces to a reasonable facsimile of U* in the Abelian case. A structure theorem for monoids of linear systems reveals the R monoid of Give'on and Zalcstein as appropriate only when no distinct powers of the statetransition matrix have the same action.
1. DECOMPOSABLE ~{'-MACHINES
We consider a linear system to be one for which U, Y, and X are all R-modules for a fixed ring R with identity and for which 3:X โข U--+X and fl:X--+ Y are R-linear, i.e., there exist R-linear maps F: X--~ X, G: U---~ X and H: X--~ Y such that the next-state map 3 and output map/3 are given by 8(x, u) = Fx + Gu, (1) /3(x) = Hx, for all x in X and u in U.
The zero-state response of the linear system(F, G, H) is given by the map f: U* --+ Y defined by k f(u k ,..., Ul) = ~ HFJ-IGuj with each u s ~ U.
(2) j=l By sacrificing the monoid structure on U* we can turn the underlying set into