THE UN I V E RS I TY O F M I CH I GAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department Technical Report A UNIFIED MINIMAL REALIZATION THEORY, WITH DUALITY, FOR MACHINES IN A HYPERDOCTRINE (Announcement of Results) E S. Bainbridge Mathematics Faculty of Science and Engineering University of Ottawa Ottawa 2, Canada with assistance from: National Science Foundation Grant No. GJ-29989X Washington, D.C. Wu E U!IVERSIT OF MIC IGA administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR June 1972

Is l - - } I em i~ v9,. i: 9

Summary This report gives a preliminary *account of a new formulation of automata and system theory. Using Lawvere's notion of a hyperdoctrine, a single unified theory encompassing the minimal realization theories of sequential machines; algebra automata; a new generalization of algebra automata to non-equationally definable theories, giving arbitrary recursive computations as behaviours; linear systems; machines with algebraic structure; and machines with restricted input; is presented. In addition, the concept of a coordinatized machine is introduced, and a duality for such machines which is closely connected to the minimal realization theory is described. Coordinatized machines with each of the above types of structure may be defined; moreover, linear systems have a natural coordinatization relative to which the general duality specializes to the Kalman duality.

0. Introduction 1. A Fundamental Example 2. Hyperdoctrines 3. A Reformulation of Machine Theory 4. Applications 5. Other Features of the Formulation 6. Duality

0. Introduction This report gives a preliminary account of results from the author!s doctoral dissertation, currently in preparation. In recent years there have been attempts to unify.the minimal realization theories of various branches of automata and system theory, notably those of sequential machines and linear systems, as in [12]. Also, attempts have been made to unify the duality of linear systems theory with the apparent duality or partial duality between reachability and observability for automata, as in [91. Last year, Goguen [21 achieved a unification of the minimal realization theories-of sequential machines and affine systems, among others; and also initiated the study of adjunctions between behaviour and realization functors. In this report I present another, quite different, formulation of machine theory which unifies automata theory and linear systems theory, and also contains a new type of duality for machines which specializes in the case of linear systems to give the familiar duality. The interesting features of this formulation are these: - The mathematical apparatus used is that of a hyperdoctrine, which was introduced by Lawvere as a model of higher

order logic, proof theory, and sheaf theory. Machines and their behaviours, as well as other features of machine theory are expressed easily and naturally using the operations of a certain hyperdoctrine. - Special cases of the type of machine considered include sequential machines; algebra automata; a new generalization of algebra automata to non-equation ally definable theories, giving arbitrary recursive computations asbehaviours; linear systems; machines with algebraic structure; and machines with restricted input. - A general miniral realization theory is developed which specializes in each of the above cases to the known theory (if any). Also, a more comprehensive set of behaviourrealization adJunctions than has previously been discussed is presented. - The notion of a coordinatized machine is introduced, and a general theory of duality for such machines is developed. These machines also have a canonical realization theory which is closely related to the realization theory of ordinary machines. Behaviour-realization adjunctions also carry over to coordinatized machines. A linear system has a natural coordinatization in this sense, and the Kalman duality is seen to be a special case of the duality for coordinatized machines. - There is considerably more mathematical structure in the hyperdoctrine considered than is actually used in the

preliminary applications. I rive;ome examples to show the system theoretic significance of some of this extra structure; and I think these examples indicate that we may expect significant new features to emerge on further investigation.

I. A. I ~I'n tdmtnt,,l l.x:lllI c. Many of thie observations of this section have been made elsewhere; but the crucial one, the use of the left and right adjoints to the forgetful functor from right actions to sets, is new. This formulation of sequential machine theory motivates the development of section 3. Let X be a monoid. We denote a right action (a, x) 1* a-x A x X - A of X on a set A by (A, -). For any set A, we may define a right action of X on the set A x X by (a, x) ~ x' = (a, xx'). The assignment A t* (A x X, ) may be extended to a functor from the category of sets to the category of right X-actions. This functor is left adjoint to the forgetful functor from X-actions to sets. For any set A, we may define a right action of X on the set AX of functions from X to A by (f ~ x')(x) = f(x'x). The assignment A + (AX, ) may be extended to a functor from the category of sets to the category of right X-actions. This functor is right adjoint to the forgetful functor from right X-actions to sets. These observations lead to an elegant formulation of machines and their behaviours, as follows.

let (Q, *) be a right action of a monoid X of inputs on a set Q of states. Let a: I + Q be a read-in function with domain I, a set of initial conditions. Let X: Q - J be a read-out function with co-domain J, a set of final conditions. Denote by sub u (this notation will be explained later) the forgetful functor from right X-actions to sets. A machine may thus be formulated as a diagram I —— + sub ux (Q, ). -- J. Using both adjunctions, we obtain (I x X, ) (Q ) (jX ) Using the right adjoint to sub ux we obtain I x X o This is precisely the behaviour of the machine, that is, the function assigning to each initial condition i E I, and each input x E X the final condition A((ai) ~ x) E J which results. Conversely, given a behaviour B I x X —+ J we have, via the right adjoint to sub u ii~~~~

Any factorization of X, say (I X, ) —---- (. (A, *) may be interpreted, using both adJunctions, as the machine I - sub ux (A, *)-+ J Furthermore, the behaviour of this machine is precisely B. Moreover, the condition that a machine T ssub ux (Q,') ) j be reachable, in the usual sense, is simply.-that sub u' I x X - Q be onto; and the condition that the machine be observable, in the usual sense, is simply that sub u' X Q J be 1 1. In the category of right X-actions, any morphism has a unique epi-mono factorization through its image ( also coimage). In particular, given a behaviour B I x X -— +J we factor i through its image

(I xX *) (JX,.) epi \ono Im Since the forgetful functor has both right and left adjoints, it preserves monomorphisms and eipmorphisms, so that the resulting machine is both reachable and observable. Indeed, it is the familiar minimal realization of B.

2. Hyperdoctrines Lawvere [. 1 introduced the notion of a hyperdoctrine to model, among other tlhings, higher order logic. Much of the terminology derives from this interpretation. Hyperdoctrines provide the appropriate setting in which to pursue the development of section 1. The use of the hyperdoctrine (cat, Sets) is not an empty generalization; it is essential to the applications we shall consider. A cartesian closed category C has finite (including empty) products; and has, for each A E Ob C a right adJoint ( )A: C C for the functor ( ) x A: C + C. The functor ( )A is called exponentiation by A. The empty product; that is, the terminal object, is denoted by 1. A hyperdoctrine consists of: - a cartesian closed category T, the category of types. - for each object X of T, a cartesian closed category P(X) called the category of attributes of type X. - for each morphism f: X - Y in T a functor sub f: P(Y) + P(X) called substitution along f. In the examples we consider, sub( ) is functorial, although in general one requires this only up to coherent natural isomorphism. - for each morphism f: X + Y of types, left and right adJoints for sub f,'f: P(X) + P(Y) and Hf: P(X) + P(Y), called respectively existential and universal quantification along f.

The hvNordoctrine which s}hal]. be of most intelest to us Is the hyperdoctrine (cat, Sets ) described below. Tl'he structllre w}hich apprea.rs i n the hyperdoctrine (cat, Sets) > w-_ii kn:own In the literature (under other names, in most cases). We omit details of the cartesian closed structure of the type and attribute categories, and of the existential and universal quantification functors. The type category is the category cat of small categories. The category P(X) oi attributes of type X is the category of set-valued functors from X, with natural transformations as morphisms. Substitution is composition: for f:. X Y,'Y: Y + Sets, sub f ( I) Y o f For each f: X + Y, sub f: P(Y) -+ P(X) has a left adJoint Ef: P(X) -+ P(Y) and a right adJoint flf: P(X) + P(Y).

10 3. A Reformulation of Machine Theory The contents of this section generalize,) and extends that of section ].,'and is new. First we recapture section 1, and then imitate that development in the hyperdoctrine (cat, Sets). A monoid X may be viewed as a category with a single object. Set valued functors from X~P, where X is a monoid viewed as a category, are precisely right actions of X (on the set to which the single object is mapped). Natural transformations are Just morphisms of right actions, as one can see from the diagram ().X Q.. f f R -I R () * X Furthermore, if 1 is the one object, one morphism category, P(1) may be identified with Sets in an obvious way. The crucial observation which establishes link between machine theory and the hyperdoctrine (cat, Sets) is the following. Define ux 1 (the only functor) Then sub ux: P(X~P) + P(1) is the forgetful functor from right X-actions to Sets. Zux: P(1) + P(X~P) assigns to each set A, the right action (A x X,.) described above. lu: P(1) +- P(X~P) assigns to each set A the right action x

(A, ) die:cr.bl. e ti((1 bove. Tlhus all of thte con:,truct;ions of sect:l.on 1 may lhe done using tlhe operations of the hyperdoctrine (cat, Sets). Indeed, we may define a machine M= (E, u, X, D, I, a, J, A) in (cat, Sets) to consist of a functor u: E - X which is onto objects, called the behaviour scheme of M (compare ux); x c Ob P(X); I, J E Ob P(E); and morphisms cz, X in P(E) of the form I - sub u J We define a morphism (h, f, k): M + M' of machines over the behavriour scheme u to consist of h: I + I', f: ~ +', k: J + J' such that the diagram I. —-—.. sub u ~ - J hi sub u f 1k I' ~- sub u ~' -. Jt commutes. We define a behaviour over u: E - X to be a morphism in P(E) of the form B: sub u. u I -+ J for some I, J E Ob P(E). We define a morphism (h, k): B + B' of behaviours over the behaviour scheme u to consist of morphisms h: I + I',k: J + J' such that the diagram

12;;ub u u T ----- J:i' 4 {k sub u I'u —-- J' B' commutes. We define the behaviour of a machine M = (E, u, X, (,, I, a, J, ) to be the morphism 6(M) = oa where' etc indicate the transforms relative to the appropriate adJunctions. We may extend B to a functor. A machine is reachable if sub u'Z is an epimorphism and observable if sub u X is a monomorphism. We can then show the Theorem. Every behaviour B: sub u E' u I * J is realized by. a unique (up to isomorphism) reachable and observalbe machine&. Denote by Mach(u), Rch(u), Obs(u), Beh(u) the categories of machines, reachable machines, observable machines, behaviours over a fixed behaviour scheme u. Then we have the following adjunctions. Some of these adjunctions have not been discussed, even in the case of ordinary machines, as far as I know. The functor au: Mach(u) + Beh(u) has a left adjoint pu: Beh(u) + Mach(u) and a right adjoint pu: Beh(u) + Mach(u). As we saw in section 1, machines which realize a given behaviour B arise from factorizations of A', uB arises from 1 B ~ u I --- 7: u I ~ —-, >1 u J

13 and in ordinary machine theory corresponds to the free monoid machine. PuB arises from Y: u T ---- It u.1 -a —- JI u J. T'his machine is the "all possible output functions" machine, with left translation as the action. The category Rch(u) is coreflective, with the coreflector'(right adJoint to inclusion) pu: Mach(u) + Rch(u) which assigns to each machine its reachable part. The category Obs(u) is reflective, with the reflector (left adjoint to inclusion) wu: Mach(u) -* Obs(u) which assigns to each machine its observable component. The restriction of Bu to Rch(u) has a right adjoint namely ju: Beh(u) + Rch(u) which assigns to each behaviour Its reduced (reachable, observable) realization. This corresponds to the behaviour-realization adjunction discussed by Goguen [ 2 ]. The restriction of Bu to Obs(u) has a left adjoint, namely Mu: Beh(u) - Obs(u) which assigns to each behaviour its reduced realization. These adJunctions may be summarized in the diagram Mach (u) U uu Beh(u)

14 Except for the lower left adjulnction, whose counterpart has been discussed by Goguen [ 2 ] for sequential machines with quite general algebraic structure on their state and input spaces, I do not know of any discussion of these adjunctions, even for ordinary machines.

15 4. Applications Suitable specializations of machines in (cat, Sets) lead to various familiar types of machine. It should be kept in mind that the preceding minimal realization theory E:V<-pct In..q1 caeI case, as well as the development which.we shall see in later sections. 44.1 Sequential machines Taking u = ux, where X is a monoid, we obtain sequential machines with input monoid X, as we have seen. 4.2 Algebra Automata 00 An Q-algebra, where 2 = u n is a unfon of disjoint n=O sets Q of n-any operation symbols, is a set A together;~~n~ with functions PA: An + A for each P E an each n. The free Q,-algebra on generators I, Q(I), where I is any set consists of expressions formed as follows: (i) I u QO C Q(I) (ii) if El' l'' E Q(I) and Q E 2n, then " *in E n(I) In particular, for any'natural number k, we define Q(k) S= ({xl,..., xk)). 00 An equational theory in a consists of a set T = u- Tk n= k where Tk is a set of formal equations of the form [ = ['

16 where if k = 0, i,' E (O0); if k > 0, i, 5' E Q(k) - 0(k-l). A T-alebra is an Q-algebra in which all equations of T are satis fied. The free T-algebra on generators I, T(I), where T is any set, is the quotient of W2(I) relative to the smallest -t'sruenrece containing all identifications which are substitution instances of equations in T. In particular, for any natural nbimber k, we define T(k) = T({xl,..., xk}). In [ 3 ] Lawvere showed how, given an equational theory T, one may define a category T in such a way that the T-algebras are precisely the product-preserving functors from T to Sets. The category T has a single object k for each natural number, and the morphisms from k to A are given by T[k, 9] = T(k) Composition in T is given by substitution of representative expressions. A right action of a monoid may be viewed as a monadic (Qi = 4 for i Z 1) algebra. Thatcher and Wright [ 4 ] initiated the generalization of automata theory to nonmonadic algebras. For a given theory T, a T-algebra automaton is a T-algebra A together with func'tions a: I + A, X: A +- J. The behaviour of the T-algebra automaton (A, a, X) is the function

17 B: T(T) + JT defined by B(E) = X(~A(a)) where EA: AI e+ A Is the function induced by evaluation of the expression 5 in A (strictly, since 5 is an equivalence class of expressions, we evaluate a representative; and this is of course well-defined since A is a T-algebra) With I, J = 2, we are using A to recognize a certain subset of the initial T-algebra T(p), as in [ 5 I. With I, J = A; ao, X = 1A, we are evaluating expressions on data from A. To formulate algebra automata as machines in (cat, Sets), let T be as above. We denote by S the skeleton (i.e., isomorphic objects are equal) of the category of finite sets. We have an embedding u: S~P - T as follows: For any function {x1,..., xk} + {xi,..., Xg} we have (f(x1),..., f(xk)) E T(Z)k that is, a morphism ~ + k in T. This gives the functor u. Sets may be viewed as T-algebras for which Q, and hence T are empty. In this case, the associated category may be seen to be S~P. That is, product preserving functors from SOP to Sets may be interpreted as sets. It is easy to see that if 4: T + Sets is a product

18 preserving functor corresponding to a T-algebra, then sub u $ is the underlying set. The left adjoint Tu is an extension of the free algebra functor, which i.s left adJoint to the forgetful functor, so Eu(I) = T(I). An algebra automaton gives us a machine in (cat, Sets) over the behaviour scheme u I O — sub u — X J where l is product preserving. Its behaviour is a functor sub u E u I + J; that is T(I) + J and may be seen to be the behaviour in the usual sense. On the other hand, given a function T(I) + J we may calculate the reduced realization. The resulting functor T + Sets may be shown to be product preserving; that is, a T-algebra, in fact, the minimal realization of [6]. 4.3 Recursive Computation Recent work by Lawvere and Tierney has made it possible to treat non-equational theories in the same way as equational theories are treated by Lawvere. Given a theory (set of sentences) T in higher order logic, one can construct a topos T (a topos is a cartesian closed, finitely bicomp].ete category in which the functor assigning to every object its set of subobJects is corepresentable) with the property that models of T are precisely the topos structure preserving functors from T to Sets. We can formulate in such a language definitions of

19 arbitrary recursive functions. (These can not be formulated in an equational theory, since they involve essentially partial operations, such as minimization). The behaviour of the analogue of an algebra automaton would be the evaluation of terms (descriptions of recursive functions); that is, the function assigning to a recursive function description and data in a model, the value of that recursive function. This generalization of algebra automata has not been discussed elsewhere. 4.4 Linear Systems It seems to me that this is a particularly convincing example, since the formulation in (cat, Sets) meshes precisely with Kalman's elegant formulation of linear systems [ 7]. In fact our formulation explains certain features of Kalman's which, as it turns out, arise as left and right" adjoints. A discrete-time, constant linear system over a field K is specified by linear maps 6: X X cO: Km+ X A: X + KP where X is a finite dimensional vector space over K. The dynamical interpretation of the system is x(t + 1) = 6x(t) + cu(t) y(t) = Xx(t)

20 m p where t E Z, x E X, u E K y E K We paraphrase the formulation of Kalman [ 7 ]. X may be interpreted as a left module over the polynomial ring Xir[& wl t.4h the action f * x = f(6)(x) where f E K[z] and f(6): X + X is f evaluated at 6 E Hom[X, XI. Therefore we may represent the linear system as a diagram Km _ X A Kp:here X underlies a K[z] action. The diagram is in the category of vector spaces over K. We now formulate linear systems as machines in (ecat, Sets). For any ring R, the modules over that ring may be defined by an equational theory (with f2 = {+}, Q1 = RI 0 = {0} and suitable equational axioms). Let TK be the category associated with the theory of K-modules for: a' fixed field K; that is, the theory of vector spaces over K. Let TK[z] be the category associated with the theory of modules over the polynomial ring K[z], There is a natural embedding u: TK - TK[z] induced by K c K[z]. We have thus represented a linear system as a diagram Km - sub uX A- KP where X is here interpreted as a K[zl]-module (since sub u

21 Ir just the forgetful funct;or from K[z] modules to K vector <.nce,.;). We can now see why Kalman must formulate his inputoutput maps as K[z]-linear maps from Km[z] to KP[[z 1]] (formal power series in z-1). We are able to show that Z u Km = Km[z] and f u KP = KP[[z- 1]]. If the behaviour of a linear system in our sense is B: sub u E u Km - KP, then the behaviour in Kalman's sense is just A: E u Km H N u KP. It follows that our reduced realization is the classical one. 4.5 Machines with Algebraic Structure One can define a tensor pr6duct of theories with the property that product preserving functors from T into the category of product preserving functors from T' to Sets e are in a 1 - 1 correspondence with product preserving functors from T @ T' to Sets. (see [101). For example, T = TK TN where TN is the theory of N-actions, where -K[z] K N N N is the monoid of natural numbers under addition. Thus if we want to consider T-algebra automata in the Ts category of T' algebras, we will have functors T + Setsand hence T @ T' + Sets.. Using the behaviour scheme T' + T ( T': (the tensor product has natural injections) we can discuss these machines in our framework. Goguen [2] has a formulation which unifies much of realization theory. (also the study of behaviour-realiza

22 tion ad,lunctions was initiated in [2]). Hle constructs a triple (monad, standard construction) in a closed mofnoidal category which is analogous to A V+ A x S* where S* is the free monoid on a set S. A machine is a diagram 1 + A + J where A is an algebra over this triple (he does not describe his construction this way). I expect that many, if not all, of his examples can be formulated in the present framework using the tensor product of theories T <) T', where T' is a theory whose algebras form the closed monoidal category, T' and T is a theory whose algebras in Sets- are the algebras over the triple. 4.6 Machines with Restricted Input Let G be the state graph of a. (non-deterministic) generator for some set of strings over the alphabet S. We define a category G having as objects the states of G and as morphisms all triples (g, a, g') where a is a string resulting from a transition from g to g'. Composition is given by (g', a', g") o (g, a, g') = (g, aas, go). For any category X, Ob X is the category with objects as in X, but only identity morphisms. Suppose G has an initial state 0 and a final state 1. Let L be the language generated by G; that is, the set of

23 all a YE *.such that (0-, a, 1): O - 1 in. - A behavlour over L is aL func tion B: I x 1,+ J for some sets I, J. For given sets I, J, B is essentially a behaviour over the scheme u: Ob G + G (the obvious functor), namely the morphism B: sub u ~ u I. J given below B I sub u u I- J 0 I I x G[O, 0] -- 1 g 4$ I x G[O, g] --- 1:- B 1 4 I x G[0, 1] -G+ J A machine M = (Ob G, u, G, ~, I, a, J,/') will be a diagram I -' — sub u P --- J 0 I 4- (O) - 1 g) 1 Such a machine can be interpreted as follows. Assign to each g C Ob G a machine with input monoid G[g, g]. When a transition from state g to state g' occurs, the machine at g is switched off and the machine at g' is switched on with an appropriate initial state. In our example, only the machine at state 1 has outputs, but we could change this if we wanted to realize a different type of behaviour.

24 5. Other Features of the Formulation We have used some powerful apparatus to formulate machine theory. So far we have not made use of much of the mathematical structure available. Here we present some examples which show that we can expect to find machine theoretic significance in this extra structure. These applications were not designed into the formulation and hence provide evidence that this is indeed an appropriate setting for much of automata theory. 5.1 State Graphs The category (cat, X) where X is a small category has as objects functors u: E + X and as morphisffhs commutative triangles E E' u \ u X The functor (cat, X) + P(X) u Z u (1E) where 1E is terminal in P(E) has a right adJoint

25 where 1 is terminal in Sets, and (1,+) has as objects morphisms 1 4 ~ x, x E Ob X and as morphisms commutative triangles x.- - v x' where i: x - x' in X.' The functor to X is projection. In the terminology of Lawvere [81, (cat, Sets) satisfies the comprehension schema.Lawvere introduced this notion to model the relation between predicates P(x) and their extensions {a I P(a)). In our case, (1,4) is just the state graph of the action (. That is, (1,4) has as objects (in the case where 4 is a monoid action.) the elements of the set on which the action is defined, and has as morphisms arrows q -— + q' where q' = q. x. The projection (1, ) + X is just the labelling of the arrows of the state graph by monoid elements; x that is, (q — + q') + x. For the other types of machines discussed in section 4, (1, ) may also be interpreted as a state graph.

Goguen [11], and the present author (independently, in unpublished work * ) have given formulations of an interconnection of systems as a diagram in a suitable category, with the resultant system being expressable as the limit of the diagram. The above adjunction is the appropriate way to relate this formulation of sustems to the better developed theory of systems with inputs as actions. 5.2 Computation Time Suppose we have a function f: Q + Q. To any q E Q and function h: Q + 2. we may assign the natural number: least n (h(fn(q)) = 1). We can call this the computation time of the program:' do f until h' when started on the data q. We may suppose without loss of generality that {q I h(q) = 1} is closed under the action of f, otherwise we replace the original f, h with the equivalent f', h' given by f' h Q + Q - + Q --- 2 f h (0) -+ Q h (1) 2 f Q -+ Q constant 1 * Private communication to Y. Give'on August 1967; also Dissertation prospectus, Department of Computer and Communication Sciences, University of Michigan, October 1968.

27 which do satisfy the-condition. We may interpret Q, f as an N-action, where N is the monoid of natural numbers under addition, with the action given by q * n fn(q). The category SetsX, where X is a small: category, is a topos (see 4.3). Thus we have a subobJect classifier Q c Ob SetsX with the property that the subobJects of.: X + Sets are in a natural 1 - 1 correspondence with morphisms D + 2 (compare characteristic functions; in Sets, a= 2) Given an element q E Q we may consider' the corresponding function q 1 sub uN(Q,') and hence. 1 ~ (Q, ) The action E uN 1 may be taken to be on N, namely m ~ n = m + n. We have a function [(Q, *:), Q] + [(N,'), E] induced by composition with q.. This assigns to every subaction of (Q,') (such as determined by h above) a subaction of (N, *). A subaction

of (N,') iS eas:i l.y -seen to be a set of the form {:"' fI m'. X }'Ail':,lme k, or the empty subaction. We may see that to h: (Q,') + Q,corresponding to h,is assigned {m I m > least k(h(fk(q)) = 1)}. Thus the function [1, sub uN(Q,.)] x [(Q,.), Q] + [I uN 1, 1] may be interpreted as assigning to each q E Q and subaction h the computation time on q of: do f until h. This may be generalized. Using the duality of the next section, the above construction (in a gereralized form) may be given a dual interpretation. Also, using the exponentiation in SetsX the above construction and its generalizati o.s can be represented internally in the category, and given a suitable interpretation.

29 6. Duality Arbib and Zeiger [9] have investigated the duality between reachability and observability for sequent-.al machines. There is a well known duality of this type for linear machines. We present here a duality of this type for general machines in (cat, Sets) which includes in a certain sense the linear machine duality as a special case. The construction is similar in part to that of [9] but involves the essential extra notion of a coordinatized' machine.. 6.1 Coordinatized Machines There is.a contravariant adjunction on the right between P(X) and P(X~P). That is, there are contravariant functors (both of which we denote by #)' P(X)_....p(X~P) such that II, of ] The functor #: P(X) + P(XOP) is the extension to a functor of the assignment op 2() (X — + Sets) -+ (XP ------ SetsP - > Sets) That is, ~ (x) = 2 We note the following relations between # and the other operations of the hyperdoctrine (cat, Sets) (sub u )# = sub u~p # (E u ~)# = n u~P,#

30 Let (*, R) be a left action of a monoid X.' The right action (*, R)# = (2R, -) i: rlven by (p ~ x)(r) = p(x * r). Suppose that elements r E R are interpreted as nodes of a network at which binary values appear. On an input signal x E X, each node receives its next value from the node x * r. The resulting right action on 2R is as above. In other words, a right action of the form (*, R) may be interpreted as that realized by a certain type of network. If (Q, -) is a subaction of (*, R)# we may say that the network (*, R) realizes the action (Q, ). We may assume that the function R + 2Q obtained by transforming Q c 2R is 1 - 1, otherwise we replace (*, Ri by the smaller network Im((*, R) + (*, 2) ) which realizes (Q, ) and has the property. Thus in general, we define a coordinatized action of X, X a small category, to be a subobject c-+ Y #, Ob P(X~P),' E Ob P(X), whose transform T + * ( is a monomorphism. A coordinatized machine K = (E, u, X, $D,, I, T,' J, X) consists of a scheme u: E - X, a coordinatized action c+ y# over X, a: I - sub u D in P(E), and X: J - sub u~P' in P(E~P), We represent a coordiriatized machine by a diagram TuuD su Y# I --- sub u ~ - sub u Y# —- J#. Note that is $ v'~ is a coordinatized action, then so is sub u.- co sub u P. The dual of the above coordinatized machine

31 I.s op OP t T -" rrli ) la;-, v s Ul)1i s II The behaviour of a coordinatized machine is th'e behaviour of its abstract part I + sub u 4 - J A coordinatized machine also has a concrete part, a network J' sub u~P' + If The fundamental result for coordinatized machines is that every behaviour of the form B: sub u E u I J has a unique coordinatized realization B such that the abstract part and the concrete part of B are both reachable. This is the co-ordinatized machine obtained as follows. Consider Z u I +Im P+ H u J# and the resulting E u J Im + (Imn) The coordinatized action is Im + Im#. We define a morphism of coordinatized actions (... Y#) ~ (,'.- V,,#) to consist of 4 — A ~' and'' — g-*' such that

32 1 C-+ T# commutes. We. can then recon:truct the counterparts of the adjunctions of section 3. However we now replace observable by addressable (has a reachable concrete part). FurtheFmore, everything is dualizable, including behaviours, and these functors commute with the dualities. 6.2 Duality for Linear Machines For linear machines, we have the following situation. Morphisms from m to n'in the category TK[z] corresponding to the theory of left K[z]-modules may be taken to be n x m matrices over K[z]. Transposition gives us-a contravariant functor 2 TK[0op functor t: TK[z] + TK[z] with t2 1. Thus TK z] is the theory of right K[z]-modules. Any K[z] module V is a vector space over K, and so we may speak of the dual vector space V*. It is easy to see that V* may be given a right K[z]-module structure. Thus given a linear machine Km sub u V _ A KP we construct a coordinatized linear machine as follows. Define V = (V* o t)#: TK - Sets, where t: TKP TK is transposition. (This amounts to V(n) = 2V ). We have the 1- 1 functions vnc 2 V

33 corresponding to vn n V, 2 X V* + 2 w;vcr (C(vl],., vn), (v,.., Vn)) is mapped to 1 if' v.(vi) = 1 and O otherwise. These give a natural trans- 1 i i formation V + V = (V* o t) which is a coordinatized action in the above sense. We have the coordinatized linear machine ~a X Km - sub u V + sub u V —-- KP. The dual of this coordinatized machine is KP _ (KP)* - sub u V* + sub u V * — + (Km)* _ Km which is precisely the coordinatized machine corresponding to the usual dual of a linear machine.

311 _Re fe.encecs [1] LAWVFRE, F. W. Adjointness in Foun(datizons, Dialectica, Vol. 23, No. 3/4 (19'69). [2] COGUEN, J. A. Discrete-time Machines in Closed Monoidal CategorIel; T, UQltrterly Report. #30, Section IIB Institute forl CHOlnltlet'l' lRe;earch, University of Chicago ":i."AWV" F,. W. Fuhctorial Semantics of Algebraic Theories, Proc. Nat. Acad. Sci. U. S. A., 50, 869-872 (1963). [4] THATCHER, J. W. and WRIGHT, J. B. Generalized Automata Theory with an Application to a Dec:ision Problem of Second Order Logic. IBM Research RC 1713 Nov. 16, 1966.'[5] EILENBERT, S. and WRIGIT, J. B. Automata in General Algebras, IBM Research Note NC 725 July- 1967. [6] ARBIB, M. A. and' GIVF'ON, Y. Algebra Automata 1: Parallel Programming as a Prolegomena to the Categorical Approach, Information and Control. [7] KALMAN, R. E. Algebraic Theory of Linear Systems, in Topics in Mathematical System Theory; Kalman, Arbib, Falb, McGraw-Hill 1969. E8] LAWVERE, F. W. Equality in Hyperdoctrines and Comprehension Schema as an Adjoint Functor. Proc. Symp. Pure Math. Vol. XVII Applications of Categorical Algebra AMS 1970. [9] ARBIB, M. A. and ZEIGER, H. P. An Automata-Theoretic Approach to Linear Systems, IFAC Symposium Sydney Australia, August 1968. [10] PAREIGIS, B. Categories and Functors Academic Press 1970(. [11] GOGUEN, J.. A. Categorical Foundations for General Systems Theory. Presented at Midwest Category Theory Seminar, New Orleans January 1969. [12] ARBIB, M. A. Automata Theory and Control Theory - A Rapprochement. Automatica, Vol. 3 pp. 161-189 (1966).

UNIVERSITY OF MICHIGAN 90 211111149 9087 3II 9015 02493 9087