T H E UN I V E RS I TY O..F M ICH I G-AN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Comunication Sciences Department HOMOMORPHIC SIMPLIFICATION OF SYSTEMS Norman Y. Foo July 1974 Technical Report No. 156 iih ^sistance fom; - Nat, n l, Siieice Found ation \\n...r -t,GJ299;89 -'W~ i n^. ~.,.,' i n <^ C^^^ L,"..j.~..:,':1...

/AC;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~. o 41W ~~~~~'''" b.' ^ * ^ ^

ABSTRACT HOMOMORPHIC SIMPLIFICATION OF SYSTEMS by Norman Yeow-khean Foo Chairman: Bernard P. Zeigler A simplification procedure for dynamical systems is one which reduces complexity and yet retains aspects of structure or behavior. An approach to establishing criteria for the goodness of simplification procedures is proposed using concepts from logic. Homomorphic simplification procedures are considered from this perspective and various instances of homomorphism schemes are tested with respect to system theoretic predicates including realizability, linearity, continuity, time-invariance and stability. In constructing the framework for this investigation a topological realization theory for systems and a measure for degrees of time-variance are developed.

ACKNOWLEDGMENTS Much of what I know about systems and computer science was learned directly or indirectly from Bernard Zeigler, Arthur Burks, John Holland, John Meyer, Arch Naylor, William Riddle and William Porter. In particular my debt to Zeigler, who provided unfailing guidance and inspiration throughout my graduate study and subsequent research, is obvious in the following pages. I am grateful to the Logic of Computers Group for partial financial support. Its members have always been willing listeners; Andrew Barto and Sudhir Aggarwal were frequent and effective critics of my conjectures. Richard Laing was a source of extracurricular wisdom. Monna Whipp transcribed my handwritten notes into beautiful typescript. Finally I wish to express my gratitude to my wife Yoke-lin for her patience and encouragement. ii 11

TABLE OF CONTENTS ACKNOWLEDGMENTS i CHAPTERS 0. SIMPLIFICATION OF SYSTEMS O.1 Realizations 3 0.2 Simplifications 4 0.3 Validity of Simplifications 4 0.4 Higher Order Validity 8 0.5 Simplification Procedures 10 0.6 Systems 12 I. INPUT SPACES 1.1 Some Systems Concepts 13 1.2 Topologies for U 16 1.3 u as a Topological Monoid 22 1.4 Functions on 2u 24 II. REALIZATION THEORY 2.1 Factorizations 26 2.2 Algebraic Theory 31 2.3 Topological Theory 36 2.4 Topological Automata 40 2.5 State Spaces 45 2.6 Automaton Semigroups 46 2.7 Noncanonical State Spaces 48 III. LINEAR THEORY AND EXAMPLES 3.1 Linear Systems 51 3.2 Examples 54 IV. INPUT-OUTPUT HOMOMORPHISMS 4.1 Semigroup Input-Output Homomorphisms 57 4.2 The Lattice of Homomorphisms 60 4.3 Topological Results 62 4.4 Linearity 63 4.5 Input-Output Homomorphism 67 4.6 Discussion 73 V. STABILITY 5.1 Lyapunov Stability 75 5.2 Asymptotic Stability 7 5.3 Bounded-Input Bounded-Output Stability 78 5.4 Feedback Stability 80 5.5 Discussion 88 iii

TABLE OF CONTENTS (Cont d) VI. EASURES OF TIME-VARIANCE 61 Tie Invariance 6,2 A First Order Measure 92 6.3 Periodic and Almost Periodic Systems 97 6-4 Homomorphisms 1 6.$S igher Order Measures 115 6.6 DiscGssin 122 VII. SOME OPN PROBLEMS 124 REFEIENCES 126 iv

Chapter 0 The art of mode.ling.and simulation has been slow in acquiring scien-'tific credentials. The reason for this is the inherent compiexity of the subject and hence the difficulty in providing a mathematical description of the activity itself. In simulation the scientific aspects are currently embedded in predominantly statistical issues concerning experimental design, random number generation, monte-carlo techniques, and nondeductive inference. It can be argued that this is so because the sources of difficulties in. simulation do not reside in the algorithmic specification of models but rather in the construction of models and the interpretation of simular experiments. An attempt should be made to provide a conceptual basis for the process of modeling and simulation in order to identify areas.where effort can be directed to substitute more science for art, in particular to mathematise those areas which are amenable to such treatment. One such attempt has been outlined by Zeigler in a series of papers ([Z1],[Z2],[Z3],[Z4]) and a forthcoming book [Z5]. We shall rely on this conceptual basis for our development without necessarily claiming that it is the best, although it is evidently both plausible and convenient. A brief summary of the aspects of Zeigler's ideas relevant to our investigations seems appropriate. Our knowledge of the external world stems from experimentation and consists of input-output (I-0) observations. Because of both spatial and temporal limitations these observations cannot be infinite in-extent. As a consequence we are unable to comprehend the entire external world but are restricted to some subset of it via a subset of all possible I-O observations. It is'this restriction that. compartmentalizes our hypotheses 1

2 about how the external world functions and gives rise to the notion of a system. The process of rationalizing about I- observations consists in positing a structure for the system, a structure which purports to account for the I-O observations which have been obtained and may be obtained in the future. Of necessity structure assignment and I-0 experimentation is interactive in practice, as i~ well argued by Mihram ([M1], [M2]). The fundamental postulate of this approach is that in fact the external world is structured, and that its structure can be at least approximately known. However, given a system and its posited structure, the complete verification of that structure cannot usually be accomplished because of the finiteness of I-0 experimentation. Hence we have the notion of an experimental frame which selects only certain aspects of the system to be verified. An experimental frame imposes a conceptual simplification of the system, giving rise to a simplified system. This pair is conveniently called the base system and the lumped system respectively. Verification then proceeds via the lumped system with respect to the experimental frame. Thus, the modeling situation involves, from this perspective, an I-0 system. Each of these systems may be given a formal description in some mathematical system theory. The choice of the theory is part of the translation process from the informal to the formal description, and hence cannot be algorithmically specified. The analogy here is with Church's thesis'which asserts that intuitively computable functions are indeed computable in a formal sense. We do likewise, and assert that every informal system has some formal counterpart. Unlike the theory of computable functions however, it is not yet known if all of the significant mathematical system theories are equivalent. But this need not unduly concern us because the subsequent development will not postulate such equivalence; rather, we shall feel free to move from one theory to another f.

3 convenience. The passage from an I-O system to a base system is called realization or identification. In a formal sense the syntheses of acceptors for various classes of languages, the design of filters to process signals according to some prescription, the construction of a molecular biological theory to account for Mendelian genetics, are all properly called realization procedures. In this broad usage of the term realization the notion of a state space is not explicitly incorporated. Indeed it is possible, as in the case of perfect band-stop filters or nondeterministic automata, that classical notions of states are dispensable. However the subsequent development will be simplified to the extent that by realization we shall mean a state realization. The relation between a base system and a lumped system will be called a simplfication. Since base systems and lumped systems yield I-0 systems in a natural way, the term simplification will also be used to refer to the corresponding relation between the two I-O systems. In fact this use of the term is the most primitive possible. More precisely however, a simplification relation between two mathematical systems presumes the existence of some complexity measure with respect to which the relation is monotone. Our investigation will be concerned with both the realization and the simplification issues. In particular we shall address ourselves to topological issues in addition to those of an algebraic nature. 0.1 Realizations The provision of a good state description for an I-O system may be viewed as a measure of economy. For causal I-O0 systems a valid state space always exists, namely the set of all past inputs to the system. This

4 hardly qualifies as a good state description because it has maximal redundancy. On the other hand the Nerode right congruence relation on this set yields a minimal state space with no redundancy, and so provides an excellent state description. Intermediate between these two descriptions lie a host of compromises, each dharacterized by a right congruence relation refining Nerode congruerce. We shall develop a theory of topo-!ogicJL realization by introducing topologies into I-0 systems. Using this theory the properties of a cdass of simplification procedures will be examined. There remain I-0 systems whichmay not be causal. For these a classical state description is not possible and the question of realization does not arise. However it is still possible to simplify such systems. 0.2 Simplifications Because the most general systems are I-0 systems we will have occasion to look at these in some detail with regard to simplifications. To keep matters simple it will be expedient to investigate only one class of simplification procedures, namely, homomorphisms. Homomorphisms will be the main topic in the later chapters. In addition, the types of systems under consideration will be restricted to non-stochastic systems. These choices reflect our current state of confidence in simplification procedures because homomorphisms and non-stochastic systems are familiar concepts, whereas more exotic procedures and systems are less so. 0.3 Validity of Simplifications. A theme which will recur throughout the investigation is that of the validity of simplification procedures. Unlike the validity of realizations, which is merely a requirement that an internal structure accounts precisely

5 for an I-O behavior, it is not immediately clear what is meant by the validity of a simplification procedure. Since verification of a lumped system is with respect to some experimental frame it is evident that validity must refer to a hypothetical set of experiments which we are prepared to conduct. In practice this is not by itself very useful because it is usually the case that complete verification necessitates an infinite number of such experiments. Hence we have recourse to statistics, to ergodicity assumptions, and the like. However, we feel that there is a more profound basis for the definition of validity which we shall now expound. Given a particular system theory T and the collection S of systems describable in that theory, we may draw up lists of n-ary predicates over S corresponding to familiar relations on and properties of systems. Each predicate selects a subset of some cartesian product of S. namely, the extension of that predicate. Some typical predicates are discussed below. The predicates which are adduced by a particular experimemtal frame consists in the formalization of the kinds of system theoretic questions which may be asked relative to that frame. The validity of a simplification procedure is judged by the preservation of properties and relations (defined by some frame) under that procedure. More precisely, let P:S + S be some map on S, 4p its associated binary predicate, i.e., qp(S,S') ++ P(S) = S', c an n-ary predicate on S; then P is directly f-valid if (S1)....(S)(( p(SS )A...A^p(SnS ))D (.(S1,...,Sn) (S,.., S S)) and P is conversely f-valid if (Sl).... (Sn) (p(SS).. ^Spi,(S,) ))> n n~~~~~

6 and P is strongly 4-valid if it is both directly and conversely ~-valid. For brevity we shall say 4-validity for direct ~-validity since this is the most common instance we shali consider. The generalization of the above concepts is immediate. Suppose Q is a collection of predicates which are meaningful in two system theories T and T', with associated system classes S and S'. Then a procedure P:S-S' is Q-valid if it is valic with respect to every j in Q, and the unprimed and primed symbols are interpreted to be in S and S' respectively. These definitions are designed to capture formally the essential meaning of valid simplification procedures. For instance, if we consider the predicates LINEAR, CONNECTED and CONTINUOUS, all of which are unary, a homomorphism h:S-S is LINEAR-, CONNECTED-, and CONTINUOUS- yalid if (S) ((h(S) = S') z ((LINEAR(S)^ CONNECTED(S)^ CONTINUOUS(S)) a (LINEAR(S')A CONNECTED(S') CONTINUOUS(S')) with the corresponding modifications for converse and strong validity. It is presumed that these three redicates characterize some experimental frame, i.e., completely and exactly specify the questions of interest. In practice no such characterization is feasible because of the adaptive, interactive and iterative nature of the modeling and simulation process. Nevertheless what we have here is an idealization of an instant of this dynamic process, and it is hoped that an understanding of this will enable us to tackle the more ambitious enterprise of modeling dyanmics with improved confidence. Several observati/ons are pertinent. Many predicates of interest are not computable in the sense of Turing. A simple example of this is the predicate LINEAR on systems defined with vector spaces over an infinite field. This observation should give pause to those who are concerned with effectiveness but it turns out that most questions of any depth

7 in systems with topology have this regretable character. (However, it may be possible to circumvent this by appealing to an abstract theory of analog computability [ P4 ] or to some kind of a measure-theoretic approximation.) Next, if S is infinite there are more predicates than we can possibly name. This is because predicates are coextensive with subsets of cartesian products of S. Given S the identity map I:S + S isi one which satisfies all conditions of predicate validity. Conversely, if a procedure P:S + S is required to be valid with respect to every predicate it has to be the identity map because it must for any S e S satisfy the assertion p(S) -z (P(S)) where % is the predicate denoting membership in the singleton set {S}. Thus every meaningful simplification procedure must be required to be valid with respect to a proper subset of all possible predicates. More is required. If P is to be a:true simplification it has to be monotonic in some complexity measure p:S + R, i.e., fp(S1,S2)D (P(S1) > P(S2)), the selection of p being part of the modeling process. If P1,P2 are two simplification procedures, and P1 is "stronger" than P2,P2 is,-valid implies P1 is ~-valid. For instance, if P2 is a homomorphism and P1 is a continuous homomorphism then P1 is stronger than P2. It should be clear that in any useful simplification some system predicates will not be preserved. An essential feature of modeling is the deliberate exclusion of properties to which the modeler is indifferent. The choice of which properties to exclude is part of the modeling process. An examination of some of the predicates quoted as examples will reveal that the language we are proposing to describe validity is very "high level". A predicate such as LINEAR presumes many concepts at a more primitive or lower level, including definitions of a vector space and a linear transformation. A CONTINUOUS predicate presumes the definitions of a continuous map, hence of a topological space. This means

that we are using the predicates las abbreviations of sentences which are really much more complex than indicated. (The advantage gained in treating high level predicates as our primitives is analogous to the advantages afforded by high level programming languages or macros.) We need not apologize for this because although it is widely accepted that all mathematics can be reduced to axiomatic set theory, most mathematics is discussed in a language using concepts at nruch higher levels. Occasionally we may have to reach inside a system S to say something about individual points within the list that describes S.I Suppose S = (K,X) where K:X + X is the system operator, X is the input and output space; then xo is a fixed point of S if Kxo = xo. To formalize assertions like this we consider formulas which are free in certain symbols. In this case let p(S,xo) be free in the symbols S and xo, to be interpreted as "xo is a fixed point of S". Then if S' is a simplification of S via P:S - S, P is i-valid if (S)(4p(S,S') D (,(S,x) = (S',x'))) where x' is the point assigned by P to x. This suggests that the earlier definition of validity is a special case of a more complex definition involving formulas. Because we are usually concerned with global properties which are characterized by predicates, this more general definition will not be emphasized. 0.4 Higher order validity. Thus far the definition of validity has been confined to first order properties of systems. In this case every simplification procedure is a homomorphism of an Q-structure (of universal algebra). Let Q be a collection of predicate letters and S, S' be the carriers of the Q-structure.

9 Then the condition for P':S + S' to be an 0-structure homomorphism is precisely what we have defined to be direct Q-validity. In the study of systems, especially with regard to questions which prompt people to model and simulate, topological and quasitopological properties are as important as algebraic properties. Many of the former are expressible in a first order languages, but some are not. In the case that a second order language is required the definition of validity has to be generalized to allow quantification over predicates (and functions in particular). To make matters more precise, suppose a(f,{,S) is a formula free in function symbol f, unary predicate letter ( and variable S. The symbol f is to be interpreted into a map f:Z + S, where Z is the integers. Then a simplification P:S + S is a-valid if (~)(f)(S)(a(f,i,S) a(P.f,~ PP,P(S))). This is a second order sentence in a 2-sorted language. More generally we would allow a number of function symbols, predicate letters (of arbitrary arity), and variables, and let P:S + S'. But the generalization is obvious. The purpose of introducing a function on Z is to allow sequences to be treated. This is adequate as long as S has the minimal structure of a separable topological space, which will always be assumed. We consider the use of nets to be of marginal advantage. There is another motivation for studying topological properties. A predicate is fuzzy if its extension has a characteristic function with values in an interval, according to Zadeh [Zal]. A fuzzy predicate such as ALMOST-LINEAR may be given a rigorous interpretation by identifying systems satisfying the LINEAR predicate, taking the quotient, and finding a topology for the quotient space which suitably "measures" nonlinearity. Such a procedure is carried out for a different fuzzy predicate in the closing chapter.

0.5 Simplification Procedures We recall several procedures in common use for the simplification of systems. Given a coordinate system on the input-output or state set for a system, each coordinate defines a variable. Omission of some variabless is one class of simplification procedures. Another class arises from the aggregation of variables. A-technique for simplification which not only clarifies structure but is also a very powerful design tool is that of hierarchical decomposition. Other modes of decomposition are also used. In fact hierarchical and lateral decomposition are often employed together. Simon [S1] ard Mesarovic, et al. [M3] contain good discussions of these. techniques. Relatively unexplored are procedures which convert stochastic to deterministic systems and vice versa although the introduction of the ubiquitous (external or internal) random "noise" in modeling is one aspect of such procedures. It is expected that results in this area will be forthcoming. In our investigation we shall be dealing exclusively with a class of procedures collectively termed "homomorphisms". The notion of a system homomorphism arose from algebraic automata theory. Basically the idea is simple. For one automaton to be a homomorphic image of another certain commutative diagrams are presented. Depending on the "strength" of the homomorphism the objects of the commutative diagrams may consist of the input, output or state sets, which may in turn be coordinatized or not. Auxiliary conditions, such as the preservation of structural dependencies in state spaces, may be imposed. The motivation for examining homomorphisms in detail stems from the conviction that they are simple yet realistic schemes for simplifition. A complex biological model has been simplified by Zeigler and Weinberg using one instance of such a scheme [Z4] and successfully simulated on a digital computer. It is not known, however, what conditions

11 on homomorphisms are really necessary and/or sufficient for different sets of system predicates to be preserved. It also turns out that many simplification procedures are instances of homomorphisms. For example, the aggregation procedures of economics, investigated in a control-theoretic framework by Aoki [Al], is a homomorphism of state automata. From another perspective homomorphisms are idealized versions of simplifications. The nearly-decomposable systems of Ando, et al. [A2], and the method of singular perturbations [W1] in applied mathematics are approximate homomorphisms in the sense of diagrams that do not quite commute. A recent paper by Park [P1] in effect applies singular perturbation techniques to achieve an approximate homomorphic simplification of metabolic networks. To anticipate things a little, suppose h:Q + Q1 is a map from a state space to another, and 6:Q + Q and 6Q1 + Q1 are autonomous state transition functions. For a homomorphism we require that h6 =!h. Suppose Q1 is a metric space with metric d. Then an approximate homomorphism will be one such that for all qcQ d(h6(q),6lh(q)) < c for some e. The time interval over which 6 and 61 are defined will be the domain of validity of the approximation. In any case strict homomorphisms arise from idealizing these approximations, with a view to establishing the scope and limits of such procedures. Every set of commutative diagrams which define a class of homomorphisms in fact define a homomorphism scheme. Instances of the scheme are obtained by providing conditions on the maps and objects. Throughout the investigation we shall be considering such instances with regard to particular schemes. An instance i of some scheme may contain all the conditions of another instance j of the same scheme. If we have a chain of such instances they may be ordered in a hierarchy. An example of such a hierarchy is the progression towards stronger

2 conditions in the instances; input-output homomorphism, homomorphism, weak structure homomorphism, string structure homomorphism [Zl]. Suppose z1 and %2 are the associated predicates of two instances of a homomorphism with *2 stronger than (. A justifying condition (see Zeigler [Z1]) is a predicate on either the base or lumped system (or both) which will allow us to deduce %2 knowing %1 that is, climb up the hierarchy. More precisely, a justifying condition on the base system is a unary predicate J such that J(S)A^I(S,S')$.2(S,S') 0.6 Systems The concept of a system was introduced earlier. Its formalization has been carried out in the literature, and we shall merely outline several possibilities here, leaving the details to later chapters. I-0 systems are considered in great detail ir functional analytic approaches to systems theory; for examples see Porter [P2], Naylor [N1], Saeks [S2], Sandberg [S3], and Wilems [W2]. Systems with state arise from both control and automata theory; for examples see Arbib ([A3],[A4]), Kalman, Falb andArbib [K1], and the enormous literature on either subject. Much of the theory has been developed for discrete time systems, and with purely algebraic structures. In the case of 1-0 systems the setting is usually continuous and the structures are analytical. In our development we shall feel free to pass from one formulation to another depending on the convenience of the situation. In particular we shall sometimes be considering systems with state and sometimes I-0 systems.

Chapter: In this and the next chapter a topological realization theory for systems is developed. This will serve as a prerequisite for linking input-output descriptions to state descriptions of systems, afid also as, part of a continuing effort to reconcile algebraic automata theory with control theory. Some systems concepts relevant to the development will be presented in the next section but for more complete discussions the following references should be consulted: Kalman, Falb and Arbib [K1], Arbib ([A3], [A4]),' Naylor and Sell [N1], and Porter ([P2], [P3]) In these two.chapters we shall focus our attention on time-invariant, causal systems. These restrictions will be relaxed in later chapters. 1.1 Some systems concepts In the later chapters we will encounter systems which are defined by an input space and an output space of time functions. The time functions are defined on (-,oo,) or on Z the set of integers, and have as range a value space. Time-invariance is easy to define using a time set (-,oo) or Z if we first define a shift operator St or S(T), acting on time functions so that (S x)(t) = X(t-T)! 0 T~~~~T for any x a function of time. We will use the notations or S(Tr) according to the desired emphasis, the latter being used whenever T is to be regarded as an argument of interest. In the first two chapters the shift T is only incidental, hence the operator will be denoted by ST, but in the closing chapter it becomes paramount, and there the operator is denoted by S(T). Suppose f: U + V is a function from an input space to an output space of time functions, and represents an input-output (IO) system where the time set is (-G,us). Then time-in13

14 variance of f is defined by A S f fS for all T. T t Suppose now the time set is to be altered to some semi-infinite interval, say [,). A reasonable yet rigorous definition of time invariance demands that we take the following route. Let U be the space of partial functions on (-j,~) such that each function xeU is defined from some t onwards, i.e., on [to). V may be likewise defined, A A subspace of U consisting of ajll functions defined on [too) is denoted A Ihr~~ A by Ut. A shift operator S will now be regarded as acting on U to produce another subpsace Ut+T, i..e., it is presumed that U is closed under {S },I the group of shift operators. The shift operator Tis slightly modified in this instance, viz., x(a-T) when a-T >t (S x)(a) -. 1 (S x)() undefined otherwise Using thiS modification the above definition for time invariance still holds. A A A Ut and U are topological subspaces of U. S is an isomorphism t t+T T i.A A between the subspaces, and we shall assume that U and U are in fact ~~~I ~ t t+T homeomorphic. Thus S is a homeomorphic isomorphism, i.e., an iseomorphism. Therefore we may record: Definition 1.1.1 A A A A system f is time-invariant if fS = S f for all T. T T Evidently, when f is time-invariant it suffices to restrict conA A A, sideration to U. We shall do this and write U for U in this context. A forward restriction function ET on U is defined by (ETa)(t) = u(t) for t[0O,T), and undefined elsewhere. The family of such functions {ET} where R is the non-negative reals, act on U to produce the set ze R + + )

15 of initial segments denoted by U. Thus each element u of U is a restricA A tion of some u of u. U is called the segment space (of U). A backward restriction function Es on U is defined likewise, restricting domains to [T,c). The binary operation of concatenation, denoted by o, is defined as follows. Suppose ul,u2eU and D(ul) = O,tl), V(u2) = [O,t2). Then ul(t) t C [O,tl) (ulou2)(t)= lu2(t-tl) t E [tl, t+t2) undefined otherwise We shall assume that under concatenation as algebraic composition U is closed. The empty segment A is an identity, and concatenation is associative. Hence. U is a monoid. Definition 1.1.2 A TA TA TAA TA A system f is causal if VuveU VTeR E u = E => E fu = E fv. U corresponds to initial substrings in automata theory. A In many applications the system f exhibits inertia in the sense that it cannot distinguish between two input elements ul and u2 which differ only on a set of (Lebesque) measure zero on R+. When such is the case may be replaced by its quotient space where input functions differing on sets of measure zero are identified. In this instance it is clear that the construction of U may be accomplished by considering segments defined on closed (or open) intervals, since the function values at the end points of segments may be arbitrarily altered. This will be assumed whenever (Lebesque) measure is placed on R. In other applications it may be desirable to place more structure ~A A on U, for instance U may consist of piece-wise continuous functions. In this particular case it is clear that the monoid structure of U remains

16 intact. Our concern later is to establish some cases when the algebraic monoid structure is embellished to a topological monoid structure. Particular instances of topologies on U which will be considered in the sequel will be defined as the situation arises. The system f is linear when L andY have the structure of linear spaces, and f is a linear trans ormation.;Moie generally f is a A A A homomorphism when U and Y have lgebraic structures and f is an algebraic A homomorphism (preserving the st'ructure). The system f is continuous if f is continuous. 1.2 Topologies for U The segment space U may be topologized in: several ways giving rise to different modes of convergence. It is pertinent to ask what is meant by the assertion that a collection of segments converges to a given segment. To answer this a different way of looking at segments is explicated. (Dugundji [D4] is a good reference for topology.) A A Consider the cartesian product U x R. The relation p on U x R + + defined by (U,tl)p (2,t2) <=> t = t2 and ul = u21 is an[Oequivalee re. T e,t) [O,t2h is an equivalence relation. There is a bijection between the quotient space U x R+/p and the segment space U given by [(ut)] + E U. That this is indeed a bijection is easily verified. In fact this bijection A is a monoid isomorphism between U x R+/p and U, with the concatenation operation on the first space defined in the obvious way. A Now, U has a function space topology while R has several possible topologies. (For discrete-time systems, Ra may be replaced by Z, which is given the discrete topology). It is natural to equip

17 U x R with the product topology and hence U x R /p with the quotient A topology from U x R+. In this way the segment space is topologized in a natural manner. Note that the inverse image of a segment [(u,t)]p A AA A in U x R is a set ((v,t)l[t ) = ul, t)} + [Olt)'[Ot) Let U and Y be the value spaces associated with the input and ^ A output spaces U and Y respectively (and hence of U and V). We now specialize the development to the case where at least U is a metric space with a metric d. It may in fact be shown that the theory can be generalized to the case where U is a uniform space or simply a topological space, but this would complicate many proofs and obscure the essentially simple ideas on which the theory is based. The metric d in U induces a metric d' in U as follows: d(,u2) = sup d(l(t),2(t) tER In fact, d' is a generalized metric since it is a map into the extended non-negative reals. We shall write d for any metric when no confusion can arise. It is noted that a metric d on u may indeed arise without reference to the metric (if any) on U. For our purposes either point of view is acceptable. Theorem 1.2.1 A A The natural projection p:U x R+ U x R+/p is both continuous and open. Proof: Continuity follows by definition of the quotient topology. Let 6 x N be a basic open set in U x R+, i.e. 0 = {uld(G o)<e, uosU} and N = (tl,t^). Then p(6 x N) = {[;,t)]: t C (tl,t2) and

.re:cted!t^ [.O,:t) d.io.)<c} so that p lp(e x N) ={ i(Gt0)lt'A -1 and d (l B }- "Let'be an el<ment in it. Then 4Ao^>, V7, d,?o') -=.e-: ~whee!k >.Q. IThe set:0' -x N',.whe. e. e' =.;-,) < k/2.} and N' = (.tl,).contains v, and is containedi in pt::(p ic:N, so lihat.the latrter is open. Th s p(6 x:N) is open,, Aandp xi-s qpn. in the,abiove proof.it was tacyitly assumed that the'tqpoiogy on IR is the iusual. onee. Suppose ir stead -the topology:onR -was the dis.cete tpoilQg y. Then -every:::oint is open. An.examination of the proof,shows rthast the itheorem is also valid in this caae. INow -we -are in a position to -;answer tthe question posed at the [beginnir of this s.ection. First., it is obseerved that both the usual and the discrete topologies on R+ are metric topologie:., given respectively by d(t.,t2) = j:tl —t2. and d(tl,t,2) = 1 for all tlt2. Since UA is a metric space it A A follows that U x R is a metric space. However, in general U x R /p +;+ is not metrizable, although it 4ay be made so in a somewhat contrived fashion to be described later.. Nevertheless it is not necessary to use the language of filters or nets when discussing convergence-because';: it turns out that'U x;R /p U is ifirst-countable,, hence sequences are sufficient. To prove fi$rst-countability, note that p is open and continuous implies that open sets in VU are precisely the images of open sets ~~~~~.A A in U x R. U x R'is first-countable because it ismetric space. Hence U is first —countab:le, -an8d $sequences are adequate.'Let {un} be a sequene.:onvmerging to u in U, and suppose R+ has the usual topology. Let ((u,.t):E p -(U) and 6 x N be a basic neighborhood -of (uX,t), i.e., 08 i.s -an.^sball about u and t e N, an open interval. Then p(.e'x N) i:s -a neighborho.od.of'u by tthe theorem just proved, so "that {un}:must -eventually lie -in,p(e x N). The.preimage of u nunder ~~~~~~~~~~nn

19 p is a set,t) U [O ltn ) so each element n of the preimage is associated with the same tn. Thus, to say that {un} is eventually in p(e x N) is to say that (i) tn + t and (ii) ~n~~~ A Etu Etu where Zu and u are in the preimages of u and u respectively. n n n If instead the discrete topology for R was used, then condition (i) is modified to t = t eventually. In this case U is metrizable in a trivial way, namely, a, generalized metric d is definable by 00 if P(u) DV(v) d(u,v) = d (u, v) otherwise, In this case an alternative approach to topologizing U is possible, corresponding to a constructive specification of U from U: let U = UO' ), and then U may be regarded as the free union of {Ut} tER This free union is analogous to input space I* of automata theory, except of course that it may not be a free semigroup under concatenation. To show that this topology for U coincides with that of U x R./p when R has the discrete topology it suffices to observe that given uEU + we know that usUt for some t: an open set in U containing u is, in particular, one which is open in U and empty in all other components. We examine the consequence of the two topologies imposed on R, beginning with the discrete topology. Let {u } be a sequence in. A) -1I U x R+/p such that u + u. Let (u,t) e p (u). Observe that if ~t+ n (~,tv) c p (u) then t = t and E = E v. An open set about (u,t) v v A is 0 x{t} where 0 is some ball of radius 6 about u. It is evident u u tA A that {p lp( x{t})} = {(V,t)IEtv = Etw for some w where d(w, )<6} = {(,t)ld(Et, Etu)<6} p is open implies p(Oux{t}) is open, so un is eventually in this set. Let (un,tn) E p (u). Then t = t eventually, for otherwise u = p(un,t) cannot be in p(0ux{t}) eventually. In addition, Et n + Et

20 uniformly. For, suppose otherwise. Then there exists e > 0 and a sub' tA tA sequence {E U. } such that: d(E u E u) > s. Choosing; 6= it is clear thatt (,t) is. not in p lp(eux{ }), hence ur = p(u,t) cannot: be in,'l~' U m: ~p pi(0 x{t:}) eventually, which is. contradiction. Conversely, suppose {((n,t )} is a sequence such that-tn = tl eventually and E'tI - Et unifolmly. Let v be the extensions of Et' n n n A A A which agrees with u beyond t. en p(u t) = p(vnt). Also v u n n n uniformly, and certainly tn + t. So p(n,tn) + p(,t). n to S~ Puntn Summarizing the above discussion we state the following principle which will be used in the sequel. Theorem 1.2.2 Let U have the topology of uniform convergence and R the discrete topology. Suppose u - u. Then for a y sequence {(i,t )} such that n n n (,t) ~ p (u),and for any (u,t) with (f,t) e p (u), t = t n n n n t^: tf eventually andE u -t E u uniformly. Conversely, if {(u,tn)} is a sequence such that t = t eventually n n n and E'tn > Etu uniformly, then p(ntn) + p(,t). Next, assume that R has the usual topology. The above arguemnt may be repeated with the modificatioh that {p p(0 x N)} = {(v,tv)lt e N and d(E VE v)<6} {p p (u x Nt)} =(vtt )It F N and d(E VIE u)<6} where Nt is some open interval about t. In this case it may be verified that t + t and u + u uniformly on any closed interval [O,s] S n n [O,t). Unfortunately the-converse does not go through. However, by weakening the topology on U to that of pointwise convergence (thus insisting that a metric must exist in the space U) it is,possible to remedy this. If this is done, we have

21 Theorem 1.2.3 Let U have the topology of pointwise convergence and R the usual topology. Suppose u + u. Then for any sequence {(n,tn)} such that nn n -1 -1 (ut) p (un), and for any (u,t) with (u,t) E pl (u), t t and E u -+ E u pointwise. Conversely, if {(un,tn)} is a sequence such that t + t and n n n tA tA A E Un + E u pointwise, then p(un,t) e p(ut). n n n Before proving the theorem some remarks are in order. With the A topology of pointwise convergence on U and the usual topology on R theorem 1.2.1 must be re-established. To do this requires that we look at the images of under p of basic open sets of the form n = e x (t-e,t+e), with e = n [[ti,eil], where [[ti,oi]] = A i=l {U 6 UlU(ti) ~ ei',i open in U}. Thus f = {(u,tu) I(ti) ~ i,l1 < i < n and t U(t-E,t+c)}. We claim that lp() = {( t')t'~(t-Et+~) and v(ti) E 6 for t < t)} t <t,[[ti,0i]] x (t-C,t+e) which is open, so that p is open. To prove equality of the two sets, first observe that if p(Ul,t1) = p(u2,t2) then necessarily tl = t2. So if (v,t') E p p(M) it must be that t' ~ (t-E,t+e). Also, v(ti)E.i for t. < t', for supposing the contrary we have v(tj) 80. for some t. < t'. By assumption p(O,t') e p(f), so p(Q,t') = p(t,tu) for some tAu tA (Ut ) E (. Then by observation above t = t', and E u = E v, U U giving v(tj) ~ 0j, a contradiction. Thus the lefthand set is included in the right. The reverse inclusion is easily verified, so its demonstration is omitted.

22 It is clear that U is first countable under these circumstances. Proof of theorem: Let u + u, {(unt)} be a sequence such that ( n,tn) e p (un), n n nf n A -1 and (u,t) p- (u). Let d = 0 x (t-~,t+E) be basic open set about (up). By the result above p is open, so p(4) is open in U. un - u now implies that u is eventually in this open set, i.e., (u,tn) is - n eventually in p p((). Recall that 0 = n [[rioi]]. Claim: i=l t + t. Suppose otherwise: then there is 6 > 0 and a subsequence {t } such that tm - tl > 6. Since m m plp() = {(,tv)ltv ~ (t-e,t+e) and v(ri) E r < t } tA tA choosing c = 6 gives a contradiction. So t + t. Claim: E u -+ E u n n pointwise. Again suppose the contrary. Then there exist toe [O,t), a > 0, and a subsequence {G} such that d(u (to),u(t)) < a for each m. Choosing r. = t0 and 81 = {x ~ U d(x,u(t0)) < a} yields the required contradiction because U (t0) must eventually be in i.. For the converse part, let the hypotheses hold. Suppose p(u,tn)I n n p(u,t). Then there is an open set 0 about p(u,t) = u and a subsequence A A (u,t ) such that p(u,t) t 1 O for all m. There is a basic open set ^ m' u^ ^^ m'n 0 about (u,t) such that P(0u), = 0 [[r.,Ui ]]x (-,) u u u i=l and ( t ) ~ 0. for all m. Choose r.<t, l<i<n. This implies either m m -u 1 (i) tm t or (ii) t + t but u (r.) U U. for each m, or equivalently imn mi 1 A A tA tA u (ri) u/ri). (i) contradicts tn t and (ii) contradicts E un E u pointwise. Thus the conclusions of the converse are proved. 1.3 U as a topological monoid It was earlier noted that (U,o) is a monoid. In fact it is a cancellative monoid. When U has topological structures as given in the previous section it is possible to say more.

23 Definition 1.3.1 (S,o) as a right(left) semitopological monoid if S is both a topological space and a monoid, and o:S x S + S is continuous on the right (left) component. If it is continuous on both right and left it is called semitopological monoid, while if it is jointly continuous on both components it is called a topological monoid. The following proposition is easy to prove: Theorem 1.3.1 (U,o) is a topological monoid when U has the topology of uniform convergence and R has the discrete topology. In the case when U has the pointwise convergence topology and R the usual topology things are not quite as simple. However the following is true: Theorem 1.3.2 (U,o) is a right semitopological monoid When U has the topology of pointwise convergence and R has the usual topology. The distinction between the last two theorems reflects the difference in the power of the two modes of convergence. Without restrictions A on U theorem 1.3.2 cannot be strengthened. (See remarks on p. 25.) In the sequel we shall call the topology in theorem 1.3.1 the u-topology and that in theorem 1.3.2 the p-topology for short. In a sense the u-topology is rather more fundamental. If the system under consideration is defined on discrete time, hence taking the time set to be the integers Z, it is natural to insist that a sequence of segments converging to a given segment have domains of definition that are eventually equal, i.e., the characteristic of the

24 u-topology. Admittedly, "naturalness" is somewhat subjective, but in attempting to bend the p-topology to yield results of the same power as the u-topology we have to resort to a measure theoretic device. Topological semigroups have an extensive literature, a good bibliography being contained in [D3]. We shall have occasion to use only the most elementary properties of these objects. In the next chapter these theorems will be sometimes invoked in a rather explicit form. For reference these are stated as Corollary.1.3.1 With the u-topology, if (Unvn) - (u,v) then unov + uov. Corollary 1.3.2 With the p-topology if v + v then uov + uov. 1.4 Functions on U AA A A Every causal function f:U + Y induces a function f:U - Y in the obvious manner, i.e., if u c U and D(u) = [O,t), then f(u) =E f(u). For simplicity we shall hence forth denote the length of the domain of u by lu}, so that in this case ful = t. It should be clear that for such functions the output is synchronized with the input as a matter of convention, but this can be easily relaxed. Lemma 1.4.1 A f is continuous if f is continuous. We shall have reason to modify U to let it be the space of functions which are identified if they are equal almost everywhere (a.e.). In such a case segments may be defined over closed or open intervals without affecting any of the previous results but allowing a modifi

25 cation of the function f. For any u e U, uj. - t, the function f cannot depend on the value to the point t, so that in fact the function f induced by f may in this instance be defined by either f:U + Y or f:U + Y, recalling that Y is the value space of segments inh. These are equivalent definitions when U is a quotient space of functions identified if they are equal a.e. One significance of the identification of functions equal a.e. is that instances of the.proof scheme,,wIth this prevision aue,_s the various L spaces which pervade continuous systems theory. More to the point is that in this case theorem 1.3.2 may be strengthened to coincide with theorem 1.3.1, and hence Corollary 1.3.2 will also coincide with Corollary 1.3.1. To see this we rely on the above observation that segments may now be defined over closed intervals, the values at the end points'being irrelevant. If {u } and {v } are two n n sequences of segments converging in the modified p-topology to u and v respectively, the original difficulty of establishing pointwise convergence of {u ov } to uov arose from the difficulty of establishing convergence at the time point t = jul. Clearly this difficulty vanishes if the values at endpoints are irrelevant. Henceforth when no explicit mention is made of the choice of topologies for U it is to be understood that if a conclusion is true for the u-topology, it is also true for the modified p-topology. We can distinguish two IO system definitions. If f:U -* Y is taken as basic we have a Mealy type system: if f:U + Y is taken as basic we have a Moore type system.

Chapter 2 f"-. The theory of realizitions of time-var ing systems i.:sctnlex and _'':'p' e'. unsttlOed. Several elegant attempts to place the romsin pec U'.'. tivE haebe made ([B21, [6]), but as noted by Kalman [Ki] and othersthesattexhpts ave IOt ccesslly solved te prblem of canonicalreralinzatins. In this hapter we shall address ourselvs to the pllem of time-invaiat, causal systems, for which thealgebraic k:no — results "which are: needed.::we: shall consider time-vtrying systems in ter p 6, but not from a state space perspective. a at taknowntime ich ill permit C the detes ins wat of future outputs given fture iputs. Ith sihuldbed clear that onsly ciasal systems can be endowed with state sets. Causality in itself is an extremely general concept of a state s ystaem-:t in- t prae ti we-mean sufiie nt nformational equivalently it is coextant with the existence of a map from inputs hiven functure ioinputs.pace i own as the semigroup that only cthe ausal' systems cand we n shall examine it later our pspecti ecti.e Definition 2o 1.1 Geivaen at system f:U -o t th tre ex ise e a factp froation 26to the e-to-st I n automata t shall -examine it later from our perspectise Given a system f:-U +'Y: thriplhe (pQ,) is' a ~'ac~tation:2:6

27 of f if p:U + Q, X:Q x U Y, and x(p(u),v) = Eliuf(uov) for each p(u) E R(p), v c U. Q is called the state set. p(A) is denoted by q and called the initial state. It is noted that tp(A),.v) = f(v). In the subsequent development we shall need the notion of output functions from a state, denoted -:U + Y, and defined for p,(u) e R(p) by ( = S lul x' so that 3 = f. It is not an accident that the Mealy formulation of an automaton was chosen here. The formalisms of chapter 1 in a sense forces this choice. However, when the p-topology is chosen for U, the Moore formulation will prove acceptable. The reason for this is that in this instance U is in fact a quotient space where segments equal a.e. are identified, so that we may specify f:U + Y by alternatively specifying f:U + Y when f is causal. We omit a formal demonstration of this because it is simple but tedious. Hence for this instance we may modify the last definition. Definition 2.1.2 Given a system f:U + Y the triple (p,Q,X) is a factorization of f if p:U - Q, X:Q + Y, and the diagram f U Y commutes. Q is called the state-set. In this case again B = f. qo We shall not take pains to distinguish between Moore and Mealy formulations unless the circumstances warrant it'. It will be understood that whenever the p-topology is used for U we shall be at liberty to use the former.

28 The existence of factorizations in themselves is not sufficient to guarantee the existence of state sets with the property of determinism. For this we need p to have the characteristics of memory. Definiition 2.1..3 [A3] p:U - Q is a mlemory function if p(ul) = p(u2) => p(ulo U) = p(u2ou,) An alternative characterization of this is: Lemma 2.1.; Let M be the equivalence relation induced on U x U by ulMu2 <=> p(u1) = p(u2). Then p is a memory function if and only if M is a right congruence. Proof: Clear. We formalize the concept of determinism as Definition 2.1.4 A factorization (p,Q,A) of f:U - y is deterministic if there exists a function 6:Q x U - Q such that 6(p(u),v) = p(uov) for all p(u) E R(p) and vcU. Thus in this terminology a distinction is made between causality and determinism. The former refers to a strictly input-output characteristic. Every deterministic system is necessarily causal, but not vice-versa. What this implies is that a causal system may be non-deterministic to the extent that 6 is a non-deterministic "map" to equivalent (in the automaton-theoretic sense) states. Lemma 2.1.2 (p,Q,\) is a deterministic factorization if and only if p is a

29 memory function. Proof: (=>) Let P(ul) = p(u). Then p(ulov) = (P(),) = p(u2),v) = p(u2ov) for all vEU. (<=) Define 6(p(u),v) = p(uov). Clearly 6 is a map, for p(u1) = P(u2), P(ulov) = p(u2ov) for all veU by hypothesis. For q e Q/R(p), any arbitrary definition will suffice, say, the identity action. Suppose we begin with a right congruence M on UxU and ask when does it induce a deterministic factorization? To answer this requires two approaches, one for the Mealy and one for the Moore formulation. For c > 0 let M be the relation on UXU defined by uM v <=> Eiulf(uoz) = Ejvlf(voZ) ZeU where U = {udUJIlu < e}. It is clear that ME is an equivalence relation. Further, if e1 > E2 we have that M l ME where E is the relation "refines". 2 Then {M' >O is a linear ordering with infimum N = >0 M ~ 6>u e>0 E and supremum M = U M. For, uNv <=> uM v for each c>0, and N is an f 6>O e equivalence relation; uMfv <=> uM v for some e>0, and Mf is an equivalence relation. Moreover N is a fact a right congruence relation because uNv<=>Ve>O uM v => e>O uowQZ => VE>0 uowM vow' =>V,'owNvoW. In fact N is the Nerode equivalence which is to be explicitly defined in Definition 2.2.2. That N is the infimum follows from the fact that every M is refined by N. Similarly, since for every E>0 M t Mf, Mf is the supremum of the ordering. When a Moore formulation is permissible the above discussion may be simplified. In this case f:U + Y and Mf reduces to MO, that is UME = M0, because the relation uMfv = uM0v <>- f(u) = f(v) is refined by every M.

30 Lemma 2.1.3 A right congruence M induces a deterministic factorization (Pm U/M,XM if M refines Mf. Proof: (i) The Moore formulation: Let P:U + U/M, X:U/M Y m m u + []m [u]m f(u) We have to show f U~ Y U/M commutes, and that 6M:U/M x U + UM is well-defined. M M ([u]Mv) + [uov]M First, XM is well-defined because ulMu2 => f(u1) = f(u2) since M refines Mf. Next, M is well-defined because M is a right congruence. Finally, let ucU. Then AMPM(U) = AM[u]M = f(u), so the diagram commutes. (ii) The Mealy formulation: Let p:U + U/M, X:U/M x U Y u [u ([u]mv) + E f(u v) and S:U/M x U + U/M ([u]Mv) + [uov] It has to be shown that each map is well-defined. A is well-defined because: u Mu2 => uMfu2, and since M is a m 12 1Zf 2 right congruence, ulvMuov. So ul?VMM42?v, giving Elul of(ulovz) for zeUk, k > 0. The certainly E {f(u v) = E u f(u2ov). 6m is well-defined because M is a right congruence. Every right congruence M on UxJU associated with a deterministic

31 factorization (p,Q,X) of f certainly refines Mf. For the Moore case this is so because p(ul) = p(u2) a> xp(u1) = xp(u2) => f(u1) = f(u2). For the Mealy case, (p(u2),v) for all v = Elu If(ulov) = Eu I2f(u2ov) for all v => M Mf. Combining this with the previous lemma yields the following theorem. Theorem 2.1.1 A right congruence M on UxU is associated with a deterministic factorization if and only if M refines Mf. Henceforth all factorizations will be assumed to be deterministic unless otherwise indicated. 2.2 Algebraic Theory A given system f:U + Y may have many factorizations, and among these factorizations there may be some which are in some sense distinguished. A partial ordering (G,u) of the set g of memory functions (of factorizations) of the system is laid down by saying p,1 < p2 if the diagram U g ~"^2 P1 Q2 commutes for some surjective g:Q1 > Q2. Call peg minimal if it is minimal with respect to 4. Lemma 2.2.1 When P1 < p2 and p2 < p1, the two factorizations (PlQl,Xl) may be

32 completely identified. Proof: Since G is a partial ordering, when Pl P2 and. P2 - pl wep have Pl = P2 This equality is in fact a statement about the equi — poteicy of Q1 and Q2' because p2 < Pi => there is a surjection g:Q1 Q2 => Q2 is equipotent to a subset of Q1 and conversely, P2- ^ P1i 4Q1 is equipotent to a subset of Q2, hence by the Schroeder-Bernstein Theorem Q1 is equipotent to Q2. Thus we may completely idlentify (Pl1,QiX1) with (P2,Q2, 2). Corollary 2.2.1 Equality in the partial ordering (G,,) is an equivalence relation on factorizations. Definition 2.2.1 A (p,Q-,) factorization is reachab:le if p is surjective and U observable if the map Q:Q + y given by t(q) = 8 is injective. It is canonical if it is both reachable and observable. In the Moore formulation the observarbility criterion reduces to one concerning p:Q + Y. When p1 = p2 and either is reachable Lemma 2.2.1 states that the other is reachable. Theorem 2.2.1 A factorization is minimal if and only if it is canonical. Thus it its unique. Proof: See ([K1],IA3]).

33 Definition 2.2.2 ul,u2cU are Nerode-equivalent, written ulNu2, if S lu1lul f(ulv) = S lu1 IEIU F(u2ov) for each vsU. Theorem 2.2.2 N is a right congruence relation on U. Proof: Clear. Theorem 2.2.3 The Nerode factorization (p,U/N,X) of f:U + V given by p:U + U/N, X:U/N x U Y, where p(u) = [u] and X([u],v) = Ejulf(uov), is canonical and deterministic. Proof: See [A3]. The notation U/N for a quotient class is standard. X is well-defined because time-invariance allows the identification of all segments related by a shift. The above theorem gives in essence a reduced automaton in the Mealy sense with state transition function 6:U/N x U + U/N ([u],v) + [uov] which is well-defined because N is a right congruence.

34 -For the Moore formulation Theorem 2.2.3 may be restated as Theorem 2.2.4 "The Nerode factorization (p,U/N,x) of f:U + Y given by p:U + U/N,:U + Y where p(u) = [u] and X([u]) = f(u)is canonical and deterministic. In this case the diagram f U U/N -commutes. Example 2.2.1 f:l2 12 is defined by 2 2. (x',x,2".) _o(Y,Y2'''-) n where Yn = Z xi/r, r >1 i=l y = x (1 /r + /r...) + x2(/r + /r...) (where rearrangement was justified by the possitivity of the terms) < (x1 + x.)/(rso that in fact the range of f is in t2. Let x = (x,x2..., xkOO...) y = (y1,y2,..., YIO,O,...) xNy => xir = yi/r Suffixing a segment (1,0,0,...) to x,y, xNy =>?( x. + l)/rk1 = ( vYi + l)/re+, showing that k - E and the canonical state space is Rx Z.

35 Theorem 2.2.5 Let (P1,Ql'l) and (P2,q2,x2) be two factorizations such that P2 P1, g:Q1 - Q2' and let M1,M2 be the respective associated right congruences. Then M1 refines M2. Proof: Let u 1M1u, so that Pl(Ul) = P1(U2) -Then P2(2) = gP1U ) = gpl (u2) = P2 U2), o' uM2u2. Corollary 2.2.2 If M is the right congruence associated with. a factorizatiot then refines N (Nerode equivalence). Proof: If (PNQN,XN) is a Nerode factorization it is minimal by Theorems 2.2.1 and 2.2.3. Then PN is minimal in (g,<), and the result follows by the above theorem. Let H = {M: M is a right convergence on UxU aorresponding to a factorization of f} Let g denote the relation "refines" on H. That (H,;) is a partial ordering is clear. However a stronger assertion is true. Theorem 2.2.6 (H,r) is a complete lattice with inf H = N, and sup H = the discrete partition on UxU. Proof: For any subset {Ma} aA of H M C Mf for each a. then f)M = inf {Ma} ~A. Clearly hAM is a right congruence which refines M Thus arbitrary infina exist, hence arbitrary suprema. The remainder of the assertions are easily verified.

36 By Theorem 2.2.4 it is evident that (I,[) is ati-is ri to ((<) as lattices, revealing the theorem as a statement about a dayit between alternative characterizations. In this lattice of factorizations it is easily seen that if pl + Q is open, then p i:U U/M is open for each M refined by N. 2.3 Topo l Theo The algebraic theory of factorizations may be reinforced with the introduction of topologies on the state set. Suppose Cp,Qx) is a factorization of f:U - Y. We know from theorem 2.1.1 that there is a right congruence relation M associated with this factorization, so that U/M C Q, and U/M = Q if and only if p is surjective. The natural t6pology to place on U/M is the quotient topology through p, that is, a set e is open in U/M if p (8) is open in U. Then p:U -+ U/M is continuous. Because U/Me Q for p:U + Q to be continuous it is sufficient to say that the quotient topology on U/M is the relative topology of Q restricted to U/M. This will be assumed throughout. Example 2.3.1 In example 2.2.1 the qtotient topology for the Nerode state space may be inferred as follows. A basic open set in R x Z with the natural topology is of the form e x {m} where is an open interval and m is an integer. All preimages of this must be segments of length m. It can be shown that this set is pulled back into an open set in the segment space, and hence p relative to these topologies is continuous. Conversely, a basic open set in the segment space is mapped by p to some open set in R x Z, so in fact p is open. Hence the natural topology is the quotient topology.

37 Lemma 2.3. With the u-topology, if f is continuous (i) M is closed (ii) M[u] is closed for each usU. Proof: (i) Let (u,v) C M. Then there is a sequence (Unvn) ~ M such that (u,v) -(u,v)oEil f(UO z) = lz (Vn z) for each zEU. By continuity of monoid composition u n u, vn - > u z + v ~z for each z. E n n n n 1 and f continuous now imply Elzlf(unoz) + E zf(uoz) and Elz f(v nz) EI lf(voz), hence (u,v) e M, and M is closed. (ii) Let v E M-[u. Then there is a sequencelvn )M[u], v + v. So v oz + voz for each zEU. But E{ zfCv nO) = E{ fCvoz) so that EI zf(voz) = EI lf(vn z)) ElI f(voz), showing v E M[uJ. With the p-topology the lemma does not hold. For use in later proofs we record the following easy Lemma 2.3. 2 Let X,Y,Z be topological spaces such that r p S Z commutes, r is continuous and Z has the quotient topology. Then S is: continuous. By HomR(U) is meant the monoid of all maps U + U with right composition serving as monoid composition. The following scheme yields the right regular representation O for a monoid U.

38 For each zeU define a map Pz e HomR(U) by zU - (: u + uP z:The the map 4::U -+ HmR(U): z + jz is a monoid antimonomorpis. Thus the representation is faithful. In a topological context more can be said. With ssuitable topologies on U and HomR(U), o may be continuous, and indeed a homeonmorphism. A hoveomorphism which is also an isomorphism is called an iseomorphism. Since the u-topology for U is metizable a gtenralitd'm~tric or HomR(U) is given by = sup duC"(u), uw) u = dU z,w) Thus, $ is actually even stronger than an iseomorphisn in this case. We record this as Theorem 2.3.1 With the u-topology D is an isometric anti-monomorphism from into HomC(U)* In a more general caseian antiaonTlo irphism1aybei asseted. It turns out that this weaker version of the theorem just proved is valid for the p-topology on U if the pointwise convergence topology is chosen for HomR(U). To see this, let zn z. Then Cu) = uozn, n which by Corollary 1.3.2 converges to uoz. Thus 4 is continuous. Conversely, let n + 11 pointwise. Then pz (u) = uoz u~z = u (u) for each u. In particular, let u = A the monoid identity. Then Zn- z, Hence l is continuous, showing that. is indeed an anti-moneomorphism. This is stated as a theorem.

39 Theorem 2..3.2 With the p-topology * is an anti-moneomorphism from U into HomR (U). For a given factorization (p,Q,x) of f, the continuity of p is assured by the way Q is topologized. What about the continuity of x? In the Moore formulation the commutativity of the diagram U.____ _Y P X assures that X is continuous if and only if f is continuous (lemma 2.3.2). In the Mealy formulation things are not quite as straightforward. Here X:Q x U - Y, because x([u],v) = Elu f(uov). The notion of convergence in U/M c Q has to be carefully considered. These remarks shall serve as motivation for investigating the topological properties of state spaces. Some standard results which will prove useful are the following. Lemma 2.3.3 Let M1 and M2 be right congruences.. (or equivalences) on U- uc that M1 M2. Then the natural projections pl,p2 in 1 2 U ~ U/M2 -2 U/M1 are continuous.

40 Lemma 2.3.4 Let g:U + Y, and K denote the kernel equivalence relation on U g defined by uK v <=> g(u) = g(v). Then g g pa N U/K cormnmates, and g is continuous if and only if N is continuauos. For proofs of these lemmas any standard text on point-set topology may Be consulted. A good reference is Dugundji [D43. 2.4 Topological Automata'Using the theory developed in the previous sections a theory of topological automata will be presented. For simplicity most of the results depend on the use of the u-topoloQgy, but applies to the modified p-topology as explained in the previous chapter. The distinction between the Moore and Mealy formulation is displayed here. It will be noticed that the proofs in the latter case are almost invariably more lengthy although not much- more conceptually difficult. Lemma 2.4.1 The diagram 11Z'Z uoz U P. P U/M....U/MF [u]M [U~Z]M

41 commutes and z is continuous. Consequently VzeU [un] + [u] => [u oz] - [uoz]. Proof: Define uz by u [u] = [uoz]. This is well-defined because M is a right congruence, namely, if ulu2 E p [u], then ulMu2 so that ul zMu2 z and hence [u.z] = [u2.z]. The diagram commutes under this definition. To show continuity of z it is sufficient by lemma 2.3.2 to show that p'z is continuous. But this is true because p is continuous by definition and z is continuous by corollary 2.3.1. z It should be observed that because of the weaker conclusion of corollary 1.3.2 this is not true for the strict p-topology. In the terminology of factorizations it is seen that the mapping P acts as follows: z* *([u]) = 6([u],z) Thus, the above lemma is in fact a statement that 6:U/M x U - U/M is continuous in U/M. Lemma 2.4.2 [u1] = fu2] => [ulz] = [u2-z] for all zeU. Lemma 2.4.3 Let zn z. Then [u-zn] + [u-z] and is independent of the class n n representative u. Proof: z - z => v z + v'z by corollary 1.3.1 (or 13.2). By continuity n n of p, [v.zn] + [v.z]. Now let u e p [v] Then [u] - [v], and by the previous lemma [u.z] = [v.z] and [u.zn] = [v.z ]. Thus the convergence is independent of class representative.

42 Combining lemmas 2.4.1 and 2.4.3 leads to the following result. Theorem 2.4.1 In any factorization (p,U/M,X) of a system f the state transition function 6:U/M x U + U/M is continuous in each component. Proof: Only continuity in U need be demonstrated, but this is precisely lemma 2.4.3. This theorem is strengthened when p is open. Theorem 2.4.2 If p is open, 6:U/M x U + U/M is continuous. Proof: Consider the diagram: (u,z) uz UxU ~-. U _lU U (p x id) P U/Mx U U/M ([u],z) [uz] It is clearly commutative. Let %[uz] be an (open) neighborhood of [uz] in U/M. By the continuity of p and 0 the set 4 = 0 P (6lz is open. Let (u,z) be a preimage of uz in D. Then there is a basic open set u x 4 C I, with u e u and z e z,and D, z open in U. U Z U Z U Z (p x id) (u x z) = p x' x which is open since p is open, hence U Z U Z ([u],z) is an interior point of p4u x Z.. Thus interior points are mapped by (p x id) to interior points showing that (p x id) is open.' is open and (p x id) is open now imply (p x id) = 6 (0 [uz]) is open, so that 6 is continuous.

43 Again this proof does not go through for the p-topology. We observe that theorems 2.4.1 and 2.4.2 do not assume that f is continuous. This being so it is clear that we may now answer the question posed after theorems 2.3.2. Theorem 2.4.3 In the Mealy formulation the output function X:Q x U + y is continuous in each component if and only if f:U + y is continuous. Proof: (=>) Because f(u) = X(P(A),u). (<=) For some sequence un u and v, vou + vou by corollary 1.3.1, so f(voun) + f(v~u), hence X([v],un) = Elv f(voun) + E vf(vou). Therefore X is continuous in U. For some sequence [u ] + [u] and any z6U, by lemma 2.4.1 [UnOZ] > [uoz]. Define a map g:U + V by g(u) = Elulf(uoz) and a relation M on U such that uM v <=> g(u) = g(v), that is, M is the kernel equivalence z' z of g. It is clear that M refines M. Now apply lemma 2.3.4 with K = M g is continuous because (i) right composition by z is cong z tinuous (ii) f is continuous, and (iii) Elu is continuous. Thus n is continuous, where n[u]M = E llf(uoz). M z lul [un z] + [uoz] now imply (by lemma 2.4.1) that [unoz]M + [uoz]M', z z Hence x([u n],z) E llf(unoz) = n[Un]M [U]M Elulf(uOz) ([U] Z) Hence X is continuous in U/M. Theorem 2.4.4 If p is open, X:U/M x U + y is continuous if and only if f is continuous.

44 Proof: (<-) C~ons.ider the diagram (u3.v). X(-[u],v) g:uxu.~. UxUx (p x id) U/MU x U ( [u],v) whese g is defined by g::(u.,y) E Ij:f(uov). The diagram commurtes, g i.s Q-ntinuous sin.e f is continum-us, ad p' x i i s open.. Therefoe X is con.ti.nuous. (=>) f(u) =x(pCA):). The above proofs could be.consideably silmplified if the space U has the following property: If M is a right congruence (or equivalen.e) relation on U, and if a sequence {[u ]} in the quotient space U/M converges to [v], then there exists a sequence {x} in U converging to x in U with xn c [Un] (Trg ed as a set) and x e [v] (regarded as n...An a set). In fact a weaker condition may suffice, viz., that x can be replaced by a sequence {-yn},. each n e [v], and d(xn,yn) + 0. One example where such a property is indeed present is when U is a linear space. We discuss this in the next chapter. Definition: A semigroup act is a continuous function S x X + X where S is a topological semigroup and X is: a Hausdorff space. Wallace [D.3] and his stuents hae investigated semigroups from the viewpoint of semipgroup ac.ts. In the context of the foregoing results

45 the state U/M (or Q) is a semigroup act if U/M is Hausdorff and 6 is continuous. 2.5 State Spaces When p is open 6 is continuous, so satisfying part of the condition for semigroup acts. The other part deals with U/M, specifically with its separation properties. Here several sufficient conditions for U/M to be Hausdorff are given. Lemma 2.5.1 p is open, and U Hausdorff and M is closed => U/M is Hausdorff. Proof: See [D4], where the proof is given for M an equivalence relation, and observe that the same proof holds for M a right congruence relation. Corollary 2.5.1 p is open => 6:U x U/M + U/M is a monoid act. Proof: By lemmas 2.3.1, theorem 2.4.2, and the fact that U is Hausdorff. Lemma 2.5.2 If f is continuous and Y is Hausdorff then U/N is Hausdorff.

46 Proof: Let [U1] ~ [u2] in'U/N. Then there is a z in U such-that ([u],z) # A([u2],z). Consider the map X:U/N YV Z [u] + X([u], Z) which is certainly well-defined. Since f is continuous, by theorem 2.4.3 X is continuous. The result now follows immediately from the z assumption that Y is Hausdorff. Coro2lary 2.5.2 f is continuous and. Hausdorff => 6:U x U/N + U/N is a monoid act. Stronger separation properties are obtainable only with stronger assumptions on U, p, or f. When U has a certain structure (e.g. a Banach space) the state space U/M may have more or less structure (e.g. a Hilbert space or an Abelian group) depending on f. For examples of these situations consult the next chapter. 2.6 Automaton Semigroups The semigroup of our automaton is the semigroup S of functions SS{d6S U which map Q - Q, defined by 6 (q) = 6(q,s), and having as composition 06 s = 6. The homomorphic map p:U. + Q with s1 s2 1 2:(u);= 6 gives rise to a kernel equivalence K on U which is in fact a congruence relation called Myhill equivalence. So, algebraically, U/K is isomorphic to S. Unfortunately, without further assumptions it is not possible to assert that U/K and S are iseomorphic in the topological context. Standard results [D4] are:

Lemma 2.6.1 With the above notation, the diagram U., S: U --- ---------— e S c U/K commutes, and a is an iseomorphism if and only if' is an identification (i.e., if S has the quotient topology). Lemma 2.6.2 If U/K is compact and S is Hausdorff, then a is an iseomorphism. Theorem 2.6.1 If H is open 6 is continuous and Q is Hausdarff, U/-K -Q Q is a semigroup act. Proof: Consider the diagram: (u,v) uov 0 U x U~ - U TIxI1 U/K x U/K -,U/K ([u],[v]K) [uov]K It is commutative because K is a congruence relation. The composition ~ is continuous since U is a topological monoid, and T is continuous by definition. Because n is open it follows-that n x TI is open, and by diagram chasing it is seen that the composition n is continuous. Therefore (U/K,o) is a topological semigroup. Natural topologies for QQ are the compact-open and point-open topologies. See [D4] for details on these topologies. There is a simple relation between these topologies for S (having the relative topology) and that of U/K.

48 Lerma 2.6.3 Let p:U + U/M CQ and l:U - U/K be open. Then the map F:U/M x U/K - U/M given by F([u]M,[v]K) = [uv]M is jointly continuous. Hence the quotient topology for U/K is stronger than the coapact-open topology for S(=U/K algebraically). Proof: Consider the diagram UxU. ~ U 11 F 4/ U/M x U/K ~ U/M which commutes. F is well-defined because K refines M, that is, vKv2 => 6(q,vl) = 6(q,v2) for qeQ o => p(vl) = P(V2) => lMV2. By the familiar argument, p x 11 is open, so F is continuous. The last part of the lemma is a statement of the well known fact [D4] that the compact-open topology is the weakest topology for such joint continuity. Corollary 2.6.1 If II and p are open and S has the compact open topology then p is continuous. Proof: a is continuous, so $ is continuous. 2.7 Noncanonical state spaces Prior to this it was assumed that state spaces are quotients of the input segment space and received the quotient topology. Suppose we begin by selecting an arbitrary state space Q and some topology for it such that p1:U - Q is continuous. The continuity assumption is a very natural one because it is equivalent to insisting that two input segments "near" each other transfer the initial state to final states

49 "near" each other. The reachable portion pl(U)C Q of the state space still posesses the algebraic structure of being a quotient of U with respect to some right congruence M, but in this case it receives its topology from Q, namely the relative topology. pl(U) can also be given the quotient topology of U via p1. Call the relative topology TR and the quotientstopology TF. Because the quotient topology is the strongest such that p is continuous, in general TR is weaker than TF. If p1 is also open then TR = T, since in this case TR must be the quotient topology. As the state space of an automaton pl(U) may be reduced in the R standard manner. Denote its reduction by pl(U). Algebraically this is identical to the Nerode state space Q. Topologically, when R Pl(U) has the topology S and pl(U)R is given the quotient topology via pR:pl(U) + pl(U)R, denoted by SR, the space (pl(U),SR) need not be homeomorphic to (QN,SN) where SN is the Nerode space quotient topology N via p:U + Q = U/N. In general SR is weaker than S. The following theorem summarizes the above conclusions and introduces a characterizatii for topological uniqueness of state spaces. Theorem 2.7.1 (1) pl(U) has the cardinality as Q (2) Identifying p (U)R with QN algebraically, SR S (3) If x:p(U) + QN, then X is continuous if and only if pl(U) is homeomorphic to QN (4) x is continuous if p1 is also open.

50 Proof: p R. R x u / P1't In view of earlier results only (3) remains to be proved. This is easily done by the appropriate pulling back of open sets, using the commutativity of the above diagram. Note: A preliminary version [Fl] of the preceding theory was presented at the 7th Princeton Conference, March 1973. Attention is also drawn to an alternate theory developed by Onat and Geary [011 which came to my notice after the above investigation was completed.

Chapter 3 3.1 Linear Systems The theory developed in the preceding two chapters maybe specialized to the case when f is linear, that is, some linear structure is presumed for U and Y, and f is a homomorphism of these spaces. For q realization to be possible f is assumed to be causal. To keep matters simple we shall assume that U'and Y are normed linear spaces with the norm arising from norms in linear spaces U and Y in the way specified in Chapter 1. The resulting segment space U may be made into a linear space by the following device. (Refer to the diagram below.) For two segments u, v addition () is defined by U (-V = U' + v where u = SlvHWul and u'+v is the segment obtained by pointwise addition, and is defined on [0, vl). Scalar multiplication is defined in the obvious way. Using this scheme the zero of the space is not well-defined unless: we agree to identify every zero-valued segment. If this is done and we factor it out the resulting quotient space of U is the required linear space. We call it U'. For convenience we consider the Moore formulation, so f:U' + Y. Lemma 3.1.1 f(u) = f(S u) for all ueU, and all TeR+. Proof: Follows from the causality and linearity of f and a standard result 51

52 in systems theory [N1] which states that the zero state of.a causal linear system is unaffected by zero-valued inputs. Lemma 3.1.2 f is linear on U'. Proof: jet u, vEU with Ivl > jul and a be a scalar. f(u + av) = f(u' + av) by lemma 3.1.1 = f(u') + a(v) by linearity of f = f(u) + af(v) by lemma 3.1.1 The next result is essentially due to Kalman [K1] in.a different formulation. Lemma 3.1.3,uNv iff u ( v E ker f for u,veU'. Proof: tuNv iff f(u- z3 = f(v z) ZEU iff f(u) + f(S ulZ) = f(v) + f(SlvlZ) iff f(u) = f(v) by lemma 3.1.1 iff f(u) v)= 0 by linearity. U' may be given a norm by embedding (and extending by zero) its elements t-A into U and defining the norm of u in U' to be that of its embedding in U. We have to show that this indeed defines a norm. Given u and v in U', we first note that I lu' I = Iul lu since translation is an isometry, and hence 1u ()vl = - lu' + v|ii lu'l I + lIvlJ. Also Ilau l= lal ijujl. So indeed this is a norm. The topological theory for linear factorizations can now be derived as a special case of the more general theory. For this we require the assumption that f nd hence f be continuous.

53 The next lemma is a standard result from functional analysis [T1] paraphrased for our requirements. Lemma 3.1.4 Let U' be a normed linear space and K be a closed subspace. Then U'/K is a normed linear space with norm II[u]11 = inf Ilu + kll k K Wherever f:U' - Y is continuous the kernel K of f is closed. Hence U'/K is a normed linear space. However by lemma 3.1.3 the space U'/K is algebraically the same as U'/N. The next lemma, again a standard result, shows that they are in fact topologically identical too, so that the theory for topological realizations of linear systems is a specialization of the earlier theory. Lemma 3.1.5 The norm defined in lemma 3.1.4 generates: the quotient topology on U'/K. Further, it is well known that the natural projection p:U' - U'/K is linear and continuous in this case. Hence X:U'/K + Y must also be linear and continuous by virtue of f being so. In fact p is also open [T1]. In this instance the condition on theorem 2.4.2 is satisfied, so the state transition function 6:U'/K x U' -+ U'/K is continuous. It is easy to verify that 6 is actually linear as well. Therefore we have: Theorem 3.1.1 If f:U + Y is linear and continuous then it has a canonical state space which is linear, and the state transition and output functions are also continuous and linear.

54 3.2 1Examples A criticism of several theories of topological factorizations for causal nonlinear systems ([D1],[S2]) is that a linear space structure is posited for the canonical state space. In the previous section it was shown that this is justifiable when the input-output map is linear. Here we wish to provide some examples to illustrate the theory and show that an general the canonical state space need not be linear. Furthermore it is not clear at this moment how to tell by examining the input-output map itself whether its canonical state-space will have more or less structure than the input or output space. It appears that both possibilities exist. Example 3.2.1 f:L + is defined by (ala2,...) - (sgn(al), sgn(al+a2),...) where sgn(x) = 1 x > O.-I x < 0 0 x= 0 Then f:U + R where U are initial segments from. f is nonlinear, time-invariant, causal and discontinuous. k1 k2 u(1)Nu() <=> u.l = - u2) i=l i=l where-kl, k2 are the "lengths" of segments u(, respectively 6([u3,v) = 2 u+2v where the summations run over the "lengths" of u and v, for any us[u]. 6 is continuous A([u]) = f(u) and X is discontinuous.

55 Remarks: In this example the input space is a normed linear space. The state space is R. We have a state transition function which is continuous and the discontinuities of f are reflected in X only. Example 3.2.2 f: 2 - 2 is defined by (Xl X2"' )' (Yl'Y2 "') n where y2 =/r i=l E 2 = x(l/r + i/r...) + xl/r + /r n=l +.... (where rearrangement was justified by the possitivity of the terms) 2 2 Let x= (xl,x2,..., X,,O, x... Y= (Y1,Y2s, * * y,* Y, ~, ) k 9 _~ 2 2.k 2 91 xNy = E xi/r = y/r 22 2\+1 i=l 1 i=l Suffixing a segment (1,0,0,...) to x,y, xNy i x2 + L)/rk+l = ( ~ i + I /rQ, showing that k = f and the canonical state space is \i=l =2 k / Remarks: In this example the input space is aHilbert space but the canonical state space is not even a linear space although it is a Z module.

56 Ex-ample- 3.2.3: BC Q,) +) +PC[o,) is defied by (fx) (t) = sup x(s) if there are an even number of s<t zeros of x in [O,t)inf x(s) otherwise. s<t BC and PC are the linear spaces of "bounded continuous and piecewise contiluous functions respectively. Without going through a formal proof we can see that the canonical state space of f is R x R x (0,1}. The first R records the infinum up to t, and the second R records the supremum up to t. The set {(,1} records the condition "an even number of zeros" or "otherwisee". Observe that "otherwise" includes the cases of both an infinitely denumerable and an uncountable number of zeros. Remarks: In the previous two examples the Nerode spaces do retain a linear structure if the continuous time versions were used. Here, however, even with a continuous timure strctue the Nerode spa cannot be given a linear structure since {O,1} is simply a two element set.

Chapter 4 The concept of system homomorphism was explained in Chapter 0 as an idealization of a common technique in modeling and simulation. It was also emphasized that there are many types of homomorphisms. In this chapter we focus on input-output honomorphisms in which the input segment space map from base to lumped model is a semigroup homomorphism. From the definition given below it is seen that this corresponds to the common procedure of batching events in discrete simulation languages. For convenience we shall work with Moore-type specifications, the extension to the Mealy-type specifications being quite clear from preceding developments. 4.1 Semigroup Input-Output Homomorphisms A base system f:U + Y and a lumped system f:U1 Y1 are presumed to exist in a certain relationship which is to be defined. The notation is that of the previous chapters. Definition 4.1.1 A semigroup input-output homomorphism (sioh) from f to fl is a pair (h,k) of maps h:U + U1, k:Y + Y1 where h is a monoid homomorphism, h,k are surjective, and kf = flh. Observe that if h:U + U is a monoid homomorphism the kernel equivalence induced by h is a congruence relation, and U modulo this convergence relation is isomorphic to U1. From the results of the previous chapters we know that state spaces exist for f and fl. Given state spaces Q and Q1 for these systems respectively, and with the standard notation for state transition and output functions, denote the corresponding system representations by (U,Y,Q,6,X) and (U,Y~,Q1^,61,Xl).57

58 Definition 4.1.2 A homomorphism from (U,Y,Q,6,X) to (U1,Y1,Qi, i,1 ) is a triple (h,gk) where (h,k) is a sioh, g:Q Q1 is surjective, and 61(g(q), h(u)) = h(6(q,u)) and Xl(g(q)) = k(X(q)) for all qcQ, ueU. Historically a version of this type of homomorphism was used extensively in algebraic structure theory of automata [ H1 ]. The connection between sioh and homomorphisms was essentially observed by Zeigler [Z2] in a different context where,ioh are analogous to function homomorphisms. For completeness we shall briefly outline that development and proceed to extend it to display very satisfying algebraic and topological properties of the collection M of all sioh images of a given system. In accordance with the earlier results let us assume that Q and Q1 arise from right congruences on U and U1, and hence that these state spaces are reachable. We have already seen in section 2.2 that the state realizations associated with a given system f form a complete lattice. Here a similar result will be derived concerning M. The present situation is: UP - Ul Y p U1/M..Y where f,M1 ae r t cs on U ad where f = X.p, fl = APli and M,M1 are right congruences on U and U1. Lemma 4.1.1 The composition of two memory functions is a memory function. Proof: Clear.

S9 Corollary 4.1.1 pi'h is memory function. Proof: Semigroup homomorphisms are memory functions. This suggests that there ought to be a relationship between U/M and Ul/M1 under suitable circumstances. Indeed there is such a relationship when M1 is the Nerode-equivalence of fl. Before proceeding to elucidate it let us see what has to be shown if it is asserted that there is a map g:U/M + Ul/M which satisfies the conditions of definition 4.1.2. First, it must be the case that if uMv for u,vsU then h(u)Mlh(v). With this it follows that g may be defined by g([u]M) - pl(hu) = [hu]M1. Also kX = X g, for kX[u]M = kf(u) = XlPl(hu) = Xlg[u]M. The state transition relation is also satisfied, for g6([u]M,v) = g[uv] = [h(uv)]M = [(hu)(hv)]M = l([hu]M,hv) = 61(g[u]M,hv). Thus, to establish a homomorphism given a sioh it is sufficient to show that uMv => h(u)Mlh(v). The next lemma gives a sufficient condition for this to be the case. Lemma 4.1.2 If M = N the Nerode equivalence on U induced by fl then uMv => h(u)Mlh(v). Proof: uMv => f(uw) = f(vw) all weU => kf(uw) = kf(vw) => flh(U(w) = flh(v)) => fl[h(u)h(w)] = fl[h(v)h(w)] So h(u)N h(v).

60 Corollary 4.1.2 If (h,k) is a sioh from f to fl there exists a map g:U/: + -/N, 1 1 where: U/N is the canonical state space of fl, which makes (h,g,k) a homomorphism. The connection between these results and those of section 2..2 shoulkd be clear when h,k are taken to be the identity maps. The complete lattiice of section 2.2 is in fact a lattice of homomorphisms in the special case where the input spaces are identified, and the output spaces; are iidentified. 4.2 The Lattice of Homomorphisms The remarks concerning the lattice of homomorphisms may be generalized. It turns out that given a system f:U - Y the class M of all its I-0 homomorphic images forms a complete lattice under appropriate circumstances. When this is the case corollary 4.1.2 says that if consideration is restricted to the canonical state factorization of systems, M is in fact a complete lattice of homomorphic images of (p,U/N,), the canonical factorization of f. f is the base system and its sioh images are the corresponding lumped systems. If fl and f2 are lumped systems then a relation I is defined by saying that fl E f2 if f2 is a sioh image of fl. If the collection of lumped systems of f is denoted by C, (C,C) is a partial ordering. Let R be the complete lattice of congruence relations on U and S be the complete lattice of equivalence relations on Y, both ordered by refinement denoted by.;. Define a subset D of R x S by (R,S)eV <=> {uRv => f(u)Sf(v)Vu,veU} Lemma 4.2.1 D is a sublattice of R x S isomorphic to C.

61 Proof: Given f in C there exist maps h,k and kernel congruence R and equivalence S induced by them respectively. If uRv then h(u) = h(v), so flh(u) = flh(v). Hence kf(u) kf(v), and f(u)Sf(v). Thus (R,S)ED. Conversely, every pair (R,S)eR x S defines natural maps h,k such that (h,k) is an sioh to flU/R + Y/S. Given f2 C fl there exist pairs (R1,S1) and (R2,S2) corresponding to (hl,kl) and (h2,k2). Because fl is a homomorphic image of f2 it is clear that (R2,S2) < (R1,S1). Define the index set I by I = {ca:S ~ 2 (p)} where 12 is the projection onto the second component. If yl,y2 are in range f, say that P is f-closed if y1S Y2 for all a in I implies y1 U SaY2' a The importance of this lies in the fact that it is a condition for completeness. That P is a sublattice of R x S is in effect a restatement in input-output terms of a fact known about states in SP partitions [HI]. However, without additional hypotheses V is not a complete lattice even though R x S is complete. Theorem 4.2.1 If D is f-closed it is complete. Proof: For a collection {(R,S )}, acI an index set, such that (R,S ) is in D, we claim that (R a,Sa) is the supremum of the collection and is in D. For, uR v for each D implies f(u)S f(v) for each a, hence by f-closure f(u)Y Saf(v). Since suprema exist for arbitrary subsets, so do infima. f-closure is automatically satisfied under some conditions. A typical one is the following: consider the subset pV of p defined by D0 = { (R,S): (R,S)sD and S is a congruence on Y} This assumes that Y has at least the structure of a semigroup. The

62 Theorem 4.2.2 Do is f-closed. VD is in fact isomorphic to a sublattice C( of C where the output value map k:Y + Y1 is a homomorphism. Combining the above results we have the statements: Corollary 4.2.1 C is a complete lattice. 0 Each element of CO may be identified with its canonical (state) realization. By corollary 4.1.2 each of these realizations is a homomorphic image of the realization of f, that is, has associated with it a homomorphism (h,g,k). The partial ordering on CO is directly transferable to that on homomorphisms, so that if C' denotes the partially ordered set of homomorphic images of the realization of f, corollary 4.2.1 says that Co' is a complete lattice. 4.3 Topological Results Suppose that in definitions 4.1.1 and 4.1.2 every map was required to be continuous. An obvious question to ask is whether the preceding results still hold. This depends on the choice of topologies but if conventions chosen in the earlier chapters are adhered to the answer is yes. The proof of this is essentially an exercise in diagram chasing, and we exhibit just one sample of it, viz., corollary 4.1.2. Refering to the figure below, justified algebraically by the corollary, we have to prove that g is indeed continuous. Note: Part of the results reported in sections 4.2 and 4.4 were presented ii preliminary form [F2] at the 8th Princeton Conference, March 1974.

63 U P U/ --- y U1- > Ull /Ni: ^u P ui' \ —— I 1 An open set in Ul/N is pulled back via p1 and h to an open set in U 1 because p1 and h are continuous. g pulls back this same open set to a set 6 in U/M, but because p- (0) is open and U/M has the quotient topology, 6 is open. Hence g is continuous. Thus the corollary is also topologically valid. When X is continuous it is not necessarily the case that Xk is continuous (even though h,k are by assumption). However, it is easily verified that when lU has the quotient topology via h, X must be continuous. This is the case when h is also open. Since by 2.4.4 X is continuous if and only if f is continuous, the preceding remark gives a condition for the continuity of f! when f is continuous. 4.4 Linearity In the previous chapter it was shown that a linear f gives rise to linear transition functions and a linear state space. Suppose now we insist on sioh (h,k) where h,k are also linear. A simple result whose proof is omitted is recorded as the next lemma. Lemma 4.4.1 f linear and (h,k) linear imply fl linear. More interesting is the fact that in proceeding to a factorization with the above assumptions, g:U/M + Ul/N turns out to be linear also. ~ M i N.,

64 Lemma 4.4.2 r X. Y p q Z If r,p are linear, then q is linear. Proof: Suppose z1lz2eZ, x1,x2eX such that p(xl) = Zl, P(X2) = z2. Then q(zl) + q(z2) = qp(xl) + qp(x2) = r(xl) + r(x2) = r(x + x2) = qp(x1+x2) = q(z+z2). Also, if a is any scalar q(azl) = qp(ax) = r(axl) = ar(xl) = aqp(x1) = aq(zl). Corollary 4.4.1 Under the above assumptions g:U/M + U1/N is linear. Proof: In the commutative diagram for sioh with the linearity assumptions, p, pl'h are linear, and g forms the third part of the mapping triangle in the lemma. Corollary 4.1.2 is therefore valid in the case of continuous linear maps. An example of linear semigroup homomorphism h is now informally described. ala2, aa3 4,,6 bl b2 b3 -. In the representation above a sequence of real numbers is mapped into another sequence such that bl = al+a2, b2 = a+a, etc. The "batching" of consecutive pairs to singletons gives rise to a semigroup homomorphism.

65 Within the batch the assignment is a summation, i.e., linear. While this description can be formalized and generalized it is not considered to be terribly enlightening to do so. This technique is typical of a host of dynamic simplification methods used in modeling theory. We now turn our attention to a particular instance of homomorphism which is called aggregation in the literature. Using Aoki's [Al] formulation we shall examine the case where a linear map g:Q + Q1 exists between two finite dimensional state spaces of linear machines (A,B,C) and (A1,B1,C1). In particular it is desired to examine the relation between the spectrum of A, denoted o(A), and the spectrum of A1. The situation is (partially) depicted by: A Q A ~Q A1 Q-. Q1 Theorem 4.4.1 (Aoki) Let Aeo(A). If the eigenvectors corresponding to X are not in the kernel of g then Xea(A1). Proof: Suppose X~a(A) and q is an eigenvector corresponding to X, qg ker g. Then Aq = Xq, so gAq = Xgq Z 0. Hence Algq = Xgq, and Xea(A1). Moreover, gq is an eigenvector corresponding to X. A partial converse to this result relies on the Jordan reduction for A. Call an eigenvalue simple if it occurs in a Jordan block without off-diagonal terms. Theorem 4.4.2 If Xea(A1) and X is simple then Xca(A).

66 Proof: TT TT From gA = Alg we have A g = g A. Without loss of generality assume that A is in Jordan form (otherwise reduce it and modify g accordingly). If Al is diagonal the truth of the lemma is obvious, the rows of g being eigenvectors of A. If Al is not diagonal a similar argument yields the result for simple X. The use of this theorem, besides being a partial converse inference, is to delimit the types of base systems which have known lumped systems, provided they all reside within the class of linear finite dimensional systems, and have linear homomorphisms as relations. Suppose linear systems A,A2,...,A are known to be linear homomorphic images of an'"'' n unknown A (we identify systems with their state transition matrices). Then by the lemma above we can give a lower bound on the dimension of A by counting up the number of simple eigenvalues in A1,...,An, disregarding repetitions. We conclude this section by examining the property of A being normal. Recall that A is normal if it commutes with its adjoint A*, i.e., AA* = A*A. Self-adjointness is a special case of normality. The result in the finite dimensional case is given as: Theorem 4.4.3 A A* Q ~ Q Q Q -Q Al A Q ~ ~ Q1 Q1 At~^ Q1 T 4' Ql n I- Let Q'Q1 be finite dimensional unitary spaces, A is normal and linear, g is linear, and assume that left commutative diagram holds (i.e. g is a homomorphism from A to A1). Then A1 is normal if and only if the

67 right commutative diagram holds. Proof: (<=) Suppose the diagram commutes. Then gA = Alg and gA* = Agg. It suffices to show that <AAlgllvql> = <AAlqlql> for all qleQ1. The LHS = <A1Agq,ql where gq = =<AlgA*q,ql> =<gAA*q,ql> = <gA*Aq,q> by normality of A = <A*gAq,ql> <AAlgq,ql> <A*A ql'ql (=>) Suppose Al is normal. Use the spectral theorem [ T1 ] to obtain the spectral decompositions of Al and A, i.e. m n A =.P A=R. 1 i=l i=l From gA = Alg we obtain gf(A) = f(A1)g for analytic f. Choosing f(v) = v we get f(A) = A* and f(A1) = A*, hence gA* = Ag. The extension of the above result to the infinite dimensional case will have to invoke compactness. 4.5 Input-output Homomorphisms The definition of a sioh (h,k) is predicated upon the assumption of causality and preservation of concatenation. The causality assumption is implicit in the definition of a system being a map from a segment space U to a value space Y. In many modeling situations causality is not necessary, and neither is the semigroup property. Thus we may

68 relax definition 4.1.1 to that of an input-output homomorphism (i-o homomorphism) which requires the following framework. A system is an operator K:X -- Y where X and Y are spaces of functions defined on a time set (e.g., R, Z, an ordered group, etc.), and given two systems K1,K2, an i-o homomorphism is a pair (h,k) such that hK = K k. Often we will identify X and Y for convenience. The rest of the development will be concentrating on i-o homomorphisms of this type. We hasten to add that the scheme discussed in the previous section, although it is a state homomorphism, falls within this framework, merely by letting K be identified with A, and X,Y, be identified with Q. Hence, whenever a result is stated for i-o homomorphisms it is understood that a corresponding result holds for state homomorphisms. In this section we shall consider various typical system theoretic properties which are preserved under i-o homomorphisms. Stability and time-variance have been postponed to subsequent chapters for more detailed investigation. For the rest of this section by homomorphism we shall mean i-o homomorphism. A system K:X - X has a fixed point xo if KXo = xo. The existence of fixed points is an important property in both control and computation. Theorem 4.5.1 If h is a homomorphism from K:X + X to K:X1 + X1, then if xo is a fixed point of K, hxo is a fixed point of K1. Proof: Kx = x => hKx = hx 0 O => Kihxo hx 10 The converse is generally untrue. Given a system K:X + Y, we say it has a (function-theoretic) property P if K has that property as a function space map. The following results

69 are elementary and their proofs are omitted. In each case h:X - X1 is the homomorphism from K to K1, input and output spaces being identified, the extension to an output map k:Y + Y being easy. Theorem 4.5.2 If K is linear and h is linear, then K; is linear. Theorem 4-.5.3 If K is continuous (open) and H is continuous and open, K1 is continuous (open). This condition on h imposes the quotient topology on X1. Corollary 4.5.1 If K is continuous (open), X and X1 are complete, and h is continuous and linear, then K1 is continuous (open). This follows from the open mapping theorem [T1]. In closing we consider a problem in the interconnection of systems. In doing so we shall anticipate some of the development in the next chapter. The problem consists in the question: if local linear i-o homomorphisms are known to exist between two isomorphic networks of systems, is this sufficient to assert that a global linear i-o homomorphism also exists? We shall make this more precise later. Initially the primitive composition operators are defined, and it is shown that they preserve linear homomorphisms. For simplicity we assume that the systems in a given network are defined over a single input-output space. The relaxation of this condition is not difficult except that consistency conditions on interconnection must be met. The three primitive composition operators are called series, parallel, and feedback compositions, abbreviated respectively S,P and FB'. All three are binary. Their mode of action is best described by the schematic

70 diagrams: P(K,L) (K,L) S(K,L) FB(K,L) Whenever two arrows meet- a summation is intended, and whenever they separate they denote quantities identical to the sum which is effective for that node. An interconnection of systems is obtained by a finite number of applications of these operators. A precise statement of our problem can now be made. Let G1,G2 be two directed, labelled, possibly multiple edged graphs which are isomorphic. Assume that every edge in G1 has a system and the corresponding edge in G2 has a system linearly homomorphic to it. Then we claim that every choice of global input and output nodes will result in a linear homomorphism of the overall interconnected systems. (It is evident that the type of graphs described capture essentially the interconnections permitted.) The demonstration of this proceeds via three lemmas. A notational convenience is gained by letting K —- L mean a homomorphism exists from K to L. Lemma 4.5.1 If K1 — L1 and K2 h-L2, then P(K1,K2) h P(L,L2)

71 Proof: y hx hy It is required to show that hy = (L1 + L2)hx Since y = (K1 + K2)x hy = h(K1 + K2)x = (hK1 + hK2)x = (Lh + L2h)x = (L1 + L2)hx Lemma 4.5.2 ~h h h If K1 L1 and K2 L2 then S(K1K2) S(L1L2). Proof: hx hy It is required to show that hy = L2L1hx Since y = K2Klx hy = hK2Klx = L2hKlx = L2Llhx Observe that linearity of h is not used in this case. Before proceeding to the next lemma we have to discuss a point which is reiterated in the next chapter. In a feedback composition of K1,K2, for the composed system to be well defined, (I-K2K1) must be invertible.

72 Lemma 4.5.3 h h h If K1 — L1 and K —-L2 then FB(K,K2)- FB(L1,L) Proof: x z I 1 v hx hy I' i It is required to show that -1 hy = LI(I-L2L1) hx. Because x = (I-K2K1)z hx = h(I-K2Kl)z = (I-L2L1)hz so hz= (I-L2Ll) lhx since y = K z hy = hKlz = L hz = L(I-L2L1 hx. Using these three lemmas we complete the proof by induction on the number of operators. So assume the conclusion is true for all interconnections generated by less than or equal to n operators. (The case for one operator is in lemmas 4.5.1, 4.5.2, and 4.5.3.) Observe that a network generated by n (or less) operators is itself a system, with i-o nodes where a new connection is to be made to another system. Applying lemmas 4.5.1, 4.5.2 and 4.5.3 to these two systems completes the induction. Topological consequences of this result may be obtained by appealing to corollary 4.5.1.

73 4.6 Discussion The results on the lattice of homomorphisms is interpretable as statements about the hierarchy of models of a given system, which in turn may reside in some other hierarchy. The connection to decomposable systems (e.g. Ando, et al. [A2]) is not immediate. An element of our lattice need not be a component in a decomposition. A more correct analogy is that the lattice represents hierarchical descriptions in terms of relative micro- and macro-structure. However, in special cases, for instance in considering the homomorphic images of linear systems whose state transition matrices (possibly infinite dimensional) are near diagonal, some elements of the lattice may in fact be component subsystems. We will now restate some of the results of this chapter from the perspective of system predicate validity of homomorphisms. Corollary 4.1.2 has the form of a justifying condition as explained in chapter 0. Stated in predicate terms it is REDUCED(S') I -O HOM(S,S') STATEHOM(S,S') or TOPREDUCED(S')A CONTI-OHOM(S,S'), CONT STATEHOM(S,S') or LIN REDUCED(S')A LIN I-0_HOM(S,S'). LIN STATE HOM(S,S') or TOPLINREDUCED(S') CONTLINI-0_HOM(S,S') CONLIN STATEHOM(S,S') where TOP, CONT, LIN, HOM stand respectively for topological, continuous, linear, and homomorphism, and the predicate names speak for themselves. The various forms of corollary 4.1.2 are different instances of the same scheme for i-o homomorphisms and (state) homomorphisms. In section 4.4 validity of sioh was established with respect to the LIN predicate where (h,k) were linear; LIN I-O HOM(S,S') 3 (LIN(S) 3 LIN(S')) Also shown was

74 CONT OPEN HOM(S,S') - (CONT(S) - CONT(S')) Proceeding to the examination of spectra for state transition matrices of finite dimensional systems we stated Aoki's lemma and proved lemma 4.4.3. Although these may be stated in predicate form the restrictive conditions make it cumbersome to do so.:In section 4.5 we looked at (not necessarily causal) i-o homomorphisms. Let the FIXPOINT (K,x) be a-forrmla free in-K and x. where the notation is as explained in section 0.3. If FIXPOINT (K,x) is satisfied we mean that x is a fixed point of K. It was shown that I-0_HOM(S,S') o (FIXPOINT(S,xo) ) FIXPOINT(Sl,hxo)) where h is the i-o map. Also shown was LIN CONT I-0 HOM(S,S')A COMPLETE(X)3 COMPLETE(X') 3(CONT(S) 3 CONT(S')). The next result concerns an extension theorem for local homomorphisms. We state for one of the lemmas what form the predicate validity takes and indicate the form of the overall statement. For the parallel operation we have I-0 HOM(Sl,S )^ I-0_HOM(S2,S ) v (PAR(S1,S2) > PAR(S{,SS)) and also I-o0HOM(S1,S) A I-0 HOM(S2,S2) D I-0_HOM(PAR(S1S2), PAR(Si,S2)) where PAR is the binary predicate indicating parallel composition. The first assertion is embedded in the proof of lemma 4.5.1 and the second is the homomorphism extension theorm for parallel composition. The general statement for extensions can be made recursively, having as basis two other assertions like the second one above, one for the SER (for series) and one for the FB (for feedback) predicate.

Chapter 5 In this chapter we take up the issue of validity of homomorphisms with respect to stability predicates. There are numerous definitions of system stability but we shall consider only a few of them. We omit with some reluctance the treatment of structural stability, hoping to investigate it in future research. To begin.with we shall consider autonomous state systems and Lyapunov and asymptotic stability. We conclude with an examination of feedback stability. In considering the latter it turns out that several other interesting predicates are relevant. 5.1 Lyapunov Stability Lyapunov stability was defined originally for systems governed by differential equations. The development of dynamical systems theory has allowed the definition to be considerably broadened. Here we take Lyapunov stability to presume the existence of a system with state space Q which is a normed linear space, and a state transition function S(t;to):Q + Q where t,t are the initial and final tibig. Observe that the system is autonomous. It is presumed that the system under consideration has the property that it has a zero solution, that is, q = 0 for all t is a valid trajectory of the system. In discussions of Lyapunov stability it is the stability of this trajectory that is investigated. The question asked iS whether the system is sensitive to small perturbations of this trajectory. Definition 5.1.1 (The zero "solution" of) a system is Lyapunov stable (LS) if for each to > 0 and each c~O there exists a y such that 1iqoll < y => l[6(t,to)qqol < ~ 75

76 for all t>t. 0 Theorem S5.1.1;If h:Q + Q1 is a homomorphism from system 6 to system 61 such that lh(0) = 0, and h is continuous and open, then 6 is LS implies 6 is LS.. Proof: Let B(~) denote the sphere {qeQ: I Iqlj <~}. Let ~>O be given. If we can show there exists y>0 such that for each t 0 61(t,to)B1 () C B1(~) for all t>t, the proof is complete. Because h(O) = 0 and h is continuous, given B1ls) there exists a sphere B(~') such that -l1 B(e') c h B (). 6 is LS now implies there is y'>O such that 6(t,to) B(y~) C B(e') for all t>to i,e. B(y') c 6 (t,to) B(e') 6 (t,to)h B (s) -1 =h 6 (t,t) B (~) so hB(y') C 61 (t,to) B1() But h is open, h(O) = O, so there exists a sphere B1(y) such that B1(Y) C hB(y') 6 (t,to)B1 () i.e.. l(t,to)B1(y) C B1(E) for all t>to Corollary 5.1.1 If h:Q + Q1 is a continuous linear homomorphism from 6 to 61 such that Q and Q1 are complete then 6 is LS implies 61 is LS.

-77 Proof: By the open mapping theorem [T1] h is also open in this instance. 5.2 Asymptotic Stability A common feature of many autonomous systems is the long-term decay of the state to the zero point. If-this is accompanied by Lyapunov stability we have asymptotic stability. Definition 5.2.1 A system is asymptotically stable (AS) if it is LS and for all qcQ, t ER lim 6(t,to)q = 0 t-o00 Theorem 5.2.1 If h:Q + Q1 is a homomorphism from system 6 to system 61 such that h(0) = 0, and h is continuous and open then 6 is AS implies 61 is AS. Proof: 6 is AS => 6 is LS => 61 is LS by theorem 5.1.1 Hence all that is required is to show that for all ql and t lim l1(t,to)ql = 0 t+co 6l(tto)ql = l(tto)hq for some qsQ = h6(t,t )q so lim 6-1(t,t )q = lim h6(t,t )q t-+o t->+o = h lim 6(t,to)q since h is continuous t-oO = h(0) = 0.

78 Corollary 5.2.1 If h:Q Q1 is a continuous linear homomorphism from 6 to 6 suchithat Q and Q1 are complete then 6 is AS implies 61 in AS. Proof: lAs in corollary 5.1.1. 5.3 iBounded-input bounded-output stability kBounded sets about the origin in the normed linear space X or X play.an important role in some types of stability as well as in the problem of converse validity. In keeping with the earlier notation a ball of radius M about the origin is denoted by B(M)if it isX and by B (M) if it is in X1. The use of the symbols X and X1 is deliberate because we will use this discussion to examine bounded-input bounded-output stability, when X will stand for the input (as well as:the output) space as in the previous chapter. If h:X - X1 is such that h(O) = 0, by the boundedness of h we mean I hl = sup hxll < o xcX I ix I The point to set function h implicitly defined is the proof of theorem 5.1.1 has two obvious senses of boundedness. If h takes bounded sets to bounded sets we say it is (strongly) bounded. If h applied to some bounded set U1 yields a set which contains a bounded subset U such that h(U) = U1 then we say that it is weakly bounded. Weak boundedness is relatively easy to satisfy. An instance of this is.given in the..next lemma. Lemma 5.3.1 If h:X - X1 is a continuous linear surjection and X,X1 are Banach spaces then h- is weakly bounded.

79 Proof: h X -' >X1 P X/K Refering to the commutative diagram, the following assertions are consequences of standard results in functional analysis [T1]. K, the kernel of h, is closed, and hence X/K is a normed linear space, in fact a Banach space. p is an isomorphism, and is continuous because of the open mapping theorem. Given a bounded set U1 in X1 with a bound M, ((U1) is bounded by MI Il. If x+K C )(U1) by the definition of the quotient norm in X/K, there exists k sK such that IIx+kxl < M114l1+E: and E is some fixed positive number. Now, consider the set U = {x+k: x xeh l(U1)}. If yEU, y = x+k for some xch (U1), so h(y) = h(x) hence h(U) c U. Conversely, if xleUl there is x+k eU such that h(x+kx) = h(x) =x, so U c h(U). Thus h(U) = U1. By construction U is bounded by MI} I+6. Definition 5.3.1 If K:X - X is an i-o system K is bounded-input boundedoutput (BIBO) stable if bounded input sets are mapped into bounded output sets. Theorem 5.3.1 If h:X + X1 is an i-o homomorphism from system K to system K1, h is bounded and h-1 is weakly bounded, then K is BIBO stable imples K1 is BIBO stable. Proof: Let U1 be a bounded set in X1. h-l is weakly bounded implies there exists a bounded set U in X such that h(U) = U1. Hence K1U = Klh(U) = hK(U). But by BIBO stability of K, K(U) is bounded, thus by boundedness of h, hK(U) is bounded, hence K1U is bounded.

80 Corollary 5.3.1 If h:X -* X is an i-o homomorphism from system K to system K1, X and X1 are complete, and h is linear and continuous, then K is BIBO stable imples K1 is BIBO stable. Proof: Immediate from lemma 5.3.1 and theorem 5.3.1. Other forms of bounded stability may be treated in analogous fashion. (Strong) boundedness is not as easy to achieve. In fact if h is linear h1 cannot be bounded because ker h is not bounded. If boundedness for h' holds the converse inference for BIBO stability can be made. One naive example of when h is bounded is the following: let h:R x R - R be given by x + y if y > 0 h(x,y) = 2 x - y if y < 0 Theorem 5.3.2 If h:X - X is an i-O homomorphism from system K to system K such that h is bounded and h is bounded then K is BIBO stable if and only if K1 is BIBO stable. Proof: Similar to the proof of theorem 5.3.1. 5.4 Feedback stability Another aspect of stability theory concerns the stability of nonlinear feedback systems. The literature in this area is extensive (See Damborg and Nayor [D2] for a bibliography) but our attention will be directed towards the problem of homomorphic models of such systems. The point of view we shall take in regard to feedback systems is that outlined

81 in reference [D2], primarily because normed linear spaces are much easier to deal with than the extended linear spaces of some other references. A brief discussion of the simple nonlinear feedback system is included, but for motivation the references should be consulted. x z A schematic representation of the feedback system is shown above where K:H + H is a nonlinear operator and an appropriate (normed) linear space H is chosen to represent inputs and outputs. For reasons of simplicity, and because it is easy to recover z from y (z=Ky), we shall look at the interaction between x and y, viz., (I + K)y = x. Here we make a slight change in convention from that in chapter 4. In deference to the vast literature in feedback systems the feedback loop is considered to be negative in sign. This change is actually quite immaterial but convenient for purposes of cross referencing. Definition 5.4.1 [D2] The feedback system of the Figure is feedback stable (FB) if (i) I + K is injective, (ii) I + K is surjective, (iii) (I + K)-1 is causal, continous and maps bounded sets into bounded sets. As noted in the reference, this definition divides feedback stability into five sub-issues, each of which may be examined separately (once (I + K) exists). In the modelling situation the simplification,'process is normally an attempt to capture the essential features of K. Often, the internal structure of K may give rise to a state description which may be simplified to yield a state homomorphism. If this is too difficult recourse

82 may be had to input-output homomorphisms of the type encountered earlier. The general i-o homomorphism is not adequate in the sense that in the modelling of a feedback system as in the figure, the simplification processiis clearly one of capturing the essential features of K, using a K:X + X1 in a new normed linear space. What this amounts to is that we would insist upon a structural preservation of the feedback loop as well. The preservation of structure was formalised as an insistence on the isomorphism of labelled directed graphs in the previous chapter. In the interest of readability some of that development is briefly repeated here.:Suppose we regard the i-o homomorphism as going from the Subsystem K to the subsystem K1. Taken in isolation, this says Klh = hK, where h:X - X1. Now, we claim that this gives rise to an overall i-o homomorphism from the first feedback system (S) to the second (S1), given that (I+K) and (I+K1) are both invertible. The overall system operator for S is K(I+K)- and for S1 it is K1(I+K1). To say h is an overall i-o homomorphism is to say that hK(I+K) = K1(I+K1) h. This is a consequence of hK = Klh because of the following chain of implications: Kh =hK => h+Klh = h+hK => h(I+K)- = (I+K) h => Klh(I+K) = Kl(I+K1) h whence, by Klh = hK again, we have hK(I+K) = Kl(I+Kl) h. The point to observe is that once it can be established that hy=y at the inputs to K and K1, the overall i-o homomorphism is assured. The above formal derivation may obscure this fact, so we examine it more closely. Given x,x1 such that hx=xl at the overall inputs, it is clear that

83 -1 hy = h(I+K) x 1 - lhx and Y = (I+K) x = (I+K) hx Thus hy = ylif h(I+K)1 = (I+K1) lh i.e. hK = Klh. The converse problem of beginning with an i-o homomorphism from S to S1 and deducing conditions under which this induces an i-o homomorphism from K to K is difficult in the general case. When h is linear, however, the problem is almost trivial, and no conditions on the invertin bility of (I+K) or (I+K1) need be imposed. It is simply observed that hy = h(x-z) = hx-hz = X-Z 1 1 - z So hKy = hz = hy KlY1 = Klhy and we have hK = Kh. Invertibility assumptions have been invoked rather freely. Because it is desired to investigate the conditions under which stability is preserved under homomorphisms, it is a hypothesis that S is stable, so by assumption I+K is invertible. Lemma 5.4.1 If h is an i-o homomorphism from K to K1 then I+K1 is surjective if I+K is surjective.

84 Proofs: Recall that h is a surjection by definition. Then Klh = hK -> (I+Kl)h = h(I+K), so (I+K1)h is surjective, hence I+K1 is surjective. This is one half of the invertibility condition. The other is injectivity. It is therefore relevant to see when injectivity is preserved under homomorphisms. Lemma 5.4.2 Let h be an i-O homomorphism from F:X + X to F:X1 + X1, and F is invertible, then hx = hy => hF (x) = hF (y) is a necessary and sufficient condition for F to be invertible. Proof: Since F is surjective, so is F. It suffices to show that the condition is equivalent to injectivity of F1. Sufficiency: Suppose hx/hy, but F hx=Flhy. Since Fh=hF, hFx=hFy. Let the hypothesis of the condition be hFx=hFy, then because F exists the conclusion says hx=hF F =hF Fy=hy, a contradiction. Necessity: Let hx=hy. Because F exists let x'=F x and y'=F y. It is clear that Flhx'=Flhy' since this is equivalent to hFx'=hFy', which is simply hx-hy. But F1 is injective by assumption, so hx'=hy', that -1 -1 is hF x=hF y. Corollary 5.4.1 If h is an i-o homomorphism from K to K1, I+K is invertible, then a necessary and sufficient condition for I+K1 to be invertible is hx=hy => h(I+K) x = h(I+K) ly.

Proof: h is an i-o homomorphism from I+K to I+K1. Another condition is the following for Hilbert spaces. Lemma 5.4.3 Suppose X is a Hilbert space. If h is an I-0 homomorphism from K to K1 then a sufficient condition for I+K1 to be invertible is l<hKx-hKy, hx-hy>j I lhKx-hKylJ j hx-hyJl for all x, yeX. Proof: It is easy to show [ D2 ] that I+K1 is injective if and only if 7KxKYl2 2 IKIXI-K1Y1KI1 + 2<KX-Kll X-> + 1jx1-yj 11 0 for all x1,yleH1 i.e. jlhKx-hKyJ] + 2<hKx-hKy, hx-hy> + 11hx-hyll > 0 for all x,yeH 0. (l hKx-hKyjl - I hx-hyl{)2 - I hKx-hKyl 2 - 21 IhKx-hKyj | | hx-hyJ + | hx-hy 12 jjlhKx-hKylj2 + 2<hKx-hKy, hx-hy> + 1Ihx-hyll2 if the condition is satisfied. This condition is interpretable geometrically as a prohibition of hKx-hKy and hx-hy being parallel, and does not depend on I+K being invertible. When all of h,K,K1 are linear, and K,K1 satisfy conditions appropriate to the spectral theorems ([N1], [T1]) then using the relation hK = Klh to show hp(K) = p(K1)h for all polynomials p, it is possible to deduce invertibility of I+K1 from that of I+K. The next property to consider is causality. Strictly, the discussion should take place within a framework similar to the Resolution Spaces of Porter and Saeks [P2], [S2]. It suffices for our purposes to consider the projection operator Et which acts as follows:

86 t x(s) if s.t (Etx)(s) = 0 if x>t t tFx = EtFy for x, Then recall that F:X + X is causal if E x = Ey => E Fx =E Fy for x, ysX.'By assumption (I+K)1 is causal, and it is desired to find conditions for the causality of (I+K), given K1 is a homomorphic image of K. Lemma 5.4.4 If h is an i-o homomorphism from F:X + X to F:X1 X, F is causal, h is causal, and for every xl, YlEXl t t t t Ex = E Y => 3x,yEX, hx = x, hy and E x E y Ex=El yyand Etx then F is causal. Proof: If so, EtFx = EFy as F is causal E hFx = EthFy as h is causal EtF hx = EtFhy 11 EtFlX = EtFl When both F and F! are linear, a simple criterion for causality is obtained as follows: Let XT be the set of functions with support contained in (T,oo). Then linear K:X X X is causal if and only if KXTQ XT for all T. See [Nl]. Lemma 5.4.5 If h is an i-o homomorphism from F:X + X to F:X1 - X1, F and F1 are linear, and F is causal, a sufficient condition for F1 to be causal is that hXT = X. T

87 Proof: L causal and linear => LX XT => hLXT C hXT d> KhXT hXT => KX1 X T 1T =>^ K is causal (since it is linear). Lemma 5.4.6 Under the same assumptions as in the previous lemma, if h X = 1T XT, then F is causal if and only if F1 is causal. Proof: -1 (=>) Follows from the previous lemma by h X = X => 1 -T ^T hX = X T (<=) Suppose F is not causal. Then there exists xeXT, FxfXT. Then hxX, so F hxeX1 since F is causal. Hence hFxX. This says lP I 1 1p T 1 -l h X1 f XT a contradiction. T When h is in addition time-invariant, the previous conditions reduce to hX = X and hX = X0. An example of when hX0 = X1 is satisfied 0 0o is when h is multiplicative, i.e., (hx)(t) = g(t) x(t) where g(t):V + V in the case where H consists of functions from R to V. It is easy to see that h multiplicative implies h memoryless, but not vice-versa. Continuity and boundedness predicates were discussed in sections 4.5 and 5.3 respectively. More specifically in section 4.5 we showed that if h:X - X is both continuous and open then F:X + X is continuous, and that if X and X are complete and h is linear, the contintuity alone of h is sufficient for this to be true. In section 5.3 it was shown that if h is bounded and h-1 is weakly bounded then F is bounded implies

F1 is bounded, although the terminology was somewhat different in that context. In our current discussion F is to be identified with (I+K) and F with (I+K1). We are now in a position to collect together the information in the preceding lemmas to state theorems under which FB stability is preserved through i-o homomorphisms. Because of the several conditions on each subissue these theorems will be tedious to enumerate, so we have arbitrarily selected one possibility to give the flavor of the results. Other statements may be easily culled from the lemmas. Theorem 5.4.1 If h:X + X1 is linear and satisfies the following conditions (i) hx=hy > h+K) =t = Et (i) hx=hy => h(I+K) x = h(I+K) y, (ii) x! E yl =>3x,yEX, hx=x, hy=yl and E = E y (iii) h is continuous and open, (iv) h1 is weakly bounded; then S is FB stable implies S1 is FB stable. The point to note about the FB predicate is that rather strong conditions on homomorphisms have to be invoked in order that it be preserved. This is not altogether unexpected because the introduction of feedback can radically alter the behavior of a system, and further, feedback stability is critically dependant on the nature of the feedback. This is an instance when simple homomorphisms do not appear to suffice. 5.5 Discussion We summarize the results on validity of homomorphic simplification obtained in this chapter. The abbreviations used are self-explanatory. In section 5.1 it was shown that CONT_OPEN I-O_HOM(S,S') 0 (LS(S) v LS(S'))

89 and CONT LIN I-O HOM(S,S')A COMPLETE(Q)A COMPLETE(Q') v (LS(S) = LS(S'):) In 5.2 it was shown that CONT OPEN I-O HOM(S,S') j (AS(S) v AS(S')) and CONT LIN I-O HOM(S,S' ) COMPLETE(Q) COMPLETE (Q') r (AS (S) ~ AS(S')). Next, we proved that BDD h WEAK-BDD h tIOM(S,S') (BIBO(S)~ BIBO(S')) CONT LIN I-0 HOM(S,S')A COMPLETE(X) COMPLETE (X') _ (BIBO(S) ~ BIBO(S') and BDD h BDD h HOM(S,S') (BIBO(S) <-> BIBO(S')) The final results given in section 5.4 can be cast into predicate form, one for each lemma. The predicates are however too tedious to write in complete form. In particular the conditions in the final theorem are not particularly pleasant to restate.

Chapter 6 In systems theory the concept of slowly time varying systems has led to the modelling of such systems by their time-invariant counterparts. The question of whether there are meaningful measures of degrees of time-variance in systems is, in this context, both interesting and important. Such a measure is proposed and its consequences examined in this chapter. We focus on the viewpoint that a system is an operator from a function space to another, the function -spaces consisting of functions from a time set to a linear space. For simplicity, the domain or input space is assumed to be the same as the range or output space, and is a normed linear space. The alternative viewpoint that a system is associated with a state space, implying causality of the system operator, will be only incidental in this chapter. Although our development is most concerned with deterministic systems, the theory developed may be adapted to stochastic systems. For instance, time-invariance corresponds to the stochastic concept of stationarity. 6.1 Time-invariance The framework within which we will work is reiterated below. An input-output (i-O) system is a list <K,X,Y> where X is a normed linear space of functions x:R + Y, Y itself being a normed linear space, and K.X + X is the system operator. The shift operator S(T) acts on X as follows: (S(T)x)(t) = x(t-T). It is clear that S(T) is a linear operator, in fact an isometric isomorphism on X. 90

91 Recall that the norm of an operator G on X is defined as I G1\ = sup I 4Gx4. It will always be assumed that although-any operator G may be nonlinear, G(O) = 0. An i-O system K:X + X is time-invariant if KS(T) = S(T)K for all T R. The difference KS(T) - S(T)K appears in quantum physics as the commutator of K and S(T), written [K,S(T)]. For convenience we follow this convention. Thus a system K is time-invariant if and only if [K,S(T)] for all T. A system is time-varying if it is hot time-invariant. Denote the space of all functions from X to X by [X + X]. We denote the linear space of all bounded operators on X by B(X), and the subspace of B(X) consisting of the time-invariant operators by C(X). Thus C(X) B(X) c [X - X]. A standard result [P2], [W2] is stated as the following theorem. Theorem 1.1 C(X) is a closed left-distributive subalgebra of B(X). We shall drop the qualification "left-distributive" and use the term "algebra" to mean a "left-distributive algebra" in the sequel. Of course when the systems are all linear the algebras become both leftand right-distributive. Recall that an algebra is a Banach algebra when it is closed under some topology, in this case the norm topology of the operator space; in other words the linear space structure of the algebra is a Banach space. When X is a Banach space then B(X) is a Banach algebra, and therefore so is C(X). The multiplicative operation is operator com

92 position. However C(X) is not an ideal of B(X). Despite this it is true that the quotient space B(X)/C(X) is a normed linear space (although not a normed algebra) since C(X) is a closed linear subspace. 6.2 A first order measure iBeginning with the observation that [K,S(T)] is not zero for some T in.a time-varying system K, it is natural to regard the norm of [K,S(T)] as some indication of the deviation from time-invariance for time shift T. A slight but useful modification will sometimes be made to our definition of the space X. Occasionally X will be taken to be the space of functions defined over some closed interval of R or a semi-infinite interval of R. A justification for this is that often in practice two systems are compared for their time-varying characteristics only over some finite duration of an experiment, and many systems are defined for nonnegative time only. Consider the map 4(K):R + [X - X] given by T-+ [K,S(T)]. Often this map is continuous, but continuity is assumed only when needed. Observe the map T - S(T) is sometimes not continuous in the uniform topology for B(X), although it is practically always strongly continuous. This does not preclude the continuity of 4(K) where [X + X] has the uniform topology. Example 6.2.1 If the map T + S(t) is continuous then the map 4(K) is continuous, because I KS(T+AT)-S(T+AT)K-KS(T)+S(T)KI<2 jK 11K IIS(T+AT)-S (T). Example 6.2.2 Let the linear operator K:L1(-,o) —L1 (-,oooo) be defined by the

93 singular Volterra equation t (K )(t) k(s,t)u(s)ds _-00 where k(s,t) is Lipshitz continuous with Lipshitz constant c in each of its arguments. Then /t t (KS(T)u)(t) = k(s,t)u(s-T)ds -J It-oo - f k(s+T,t)u(s)ds — CO t-T (S(T)Ku)(t) = k(s,t-T)u(s)ds J -oo So [(S () K-KS(T) - S(T+AT)K + KS (T+AT))u](t) t-T f- [k(s+T,t) - k(s,t-T)]u(s)ds ft-T-AT [k(s+z+AT,t) - k(s,t-T-AT)]u(s)ds -00 /t-T-AT -= | [k(s+T,t) - k(s+T+AT,t) - K(s,t-T) + k(s,t-T-AT)]u(s)ds J00 ^t+1fk [k(s+T,t) - k(s,t-T)]u(s)ds J t-T-AT Therefore, |IS(T)K - KS(T) - S(T+AT)K + KS(T+AT)II = sup I |S(T)Ku - KS(T)u - S(T+AT)KU + KS(T+AT)ul I 1ull-=1 ft-T-AT cIt-T. 2cATI lu(s)Ids + 2cIT. u(s)lds J -oo J t-T-AT < 4cAT -+ 0 uniformly.

94 Thus, the map ~(K) is continuous. Note: The common Lipshitz constant in both arguments can be relaxed to two different Lipshitz constants. Lemma 6.2.1 The map,(T):B(X) + R given by *(T)K = I [K,S(T)] I is a seminorm, and is an even function. Proof: l(T)(aK+L) = II[aK+L,S(T)] I Il[aK,S(T)] + [L,S(T)]t IIlI[K,S(T)]II + -I[L,S(T)]3I = lalj(T)K + (T)L Evenness is clear and its proof is omitted. Lemma 6.2.2 p(T) is a norm on B(X)/C(X). Proof: 4(T) acts on a co-set K + C(X) by l(T)(K+C(X)) = *(T)K. Thus $(T)(K+C(X)) = 0 <=> I(T)K = 0 <=> KEC(X). Denote by [a] the map B(X) + R induced as follows: [a,b] [a,b]K = sup (T)K. t[a,b] Then it is easily verified that p[ ] is also a seminorm on B(X) and a [a,b] norm on B(X)/C(X). In particular, denote by' by the induced map'R. Strictly speaking' may not be finite on [X + X] so that it may sometimes be necessary to say that' is a generalized seminorm or norm, and this will be assumed on occasion.

95 t may serve as a measure of time-invariance in systems. Suppose K,L are two systems such that KK = iL. Then we may conclude that their long-term deviation from time-invariance is the same. However ~ alone will mask some important differences between K and L in most cases. Example 6.2.3 Let K and L be in B(X) where x = C(_-,oo) (Kx)(t) = cos t.x(t) (Lx)(t) = cos 2t-x(t) Then PK = 4L = 2 but clearly K and L are periodic with different periods. This will be made more precise in the next section. Example 6.2.4 Let K and L map C(-o,oo) into itself by (Kx)(t) = tx(t) (Lx)(t) = t2x(t) Then pK = iL = I, but for each interval [a,b] it is seen that [a b L > [a,b] The above examples suggest that 4 alone is not an adequate characterization of time-variation. This is remedied in section 6.4. But first, a few remarks about ~ itself are in order. Both *(T) and p are (ordinary) norms on B(X)/C (X), and they are generalized norms only on [X - X]/C(X). This is easily seen because I KS(T) - S(T)K I < IIKS(T)I 1+1 IS(T)KI < 211 Kl since it is clear that S(T) is an isometry for each T. When B(X)/C(X) or [X + X]/C(X) is given the quotient norm relative to the operator norm, that is, IlK + C(X)iI = infli K+Cll cC (x)

96 it is well-known that this in fact yields, the quotient topology for the quotient space. The relation of this norm to that induced by r[ab] Ja,b] or ~ is as follows. Suppose {K + C(X)} is a sequence converging in the quotient norm n to {K + C(X)}, i.e., infli K - K + cli + 0. CEC(x) We have for each T and each CEC(X): II (K K)S(T) - S(T) (K -K)l I I(K -K+C)SC(T) - S(T)(K K+C) I n n n n. 21lS(T)II jlK -Cll 2llKn-K+Ci So (K -K+C(X)) = supll[K -K,S(T)]ll n n TER < 2inf II K -K+Cll + 0 CeC(x) giving the result: Lemma 6.2.3 The quotient norm on B(X)/C(X) or [X - X]/C(X) is stronger than the p-norm. This leads immediately, by a corollary to the open mapping theorem [Tl] on the equivalence of comparable norms on Banach spaces to the following result. Theorem 6.2.1 If B(X) is a Banach space, then the +-norm is equivalent to the quotient norm. In particular, this is true when X is a Banach space. So in a predominantly interesting class of systems the first measure of time-variance is in fact the natural norm of the quotient space. It

97 clearly remains true that r[ab] is a net defined on the lattice [a,b R of intervals in R, so induce a lattice of topologies on systems. The upper bound is ~ and the lower bound is the trivial topology. 6.3 Periodic and almost periodic systems Before moving to more refined measures of time-variance in systems we make a small digression into an important class of systems. In linear system theory the class of systems which are described in the usual notation by dx x A(t)x where A(t) = A(t+c) for each teR, is called periodic with period,. The properties of such systems are well-known through the Floquet theory [P3]. The theory has been developed primarily from an internal viewpoint, that is, a state system is postulated. It would be gratifying to have an input-output characterization of a system periodicity in the same way that other system-theoretic properties like causality, passivity and time-invariance are characterized, postulating only an i-O system. One possible approach is given here. Definition 6.3.1 A system K is periodic if there exists o>0 such that S(a)K = KS(c). a is called a period of the system. Observe that this is equivalent, in our notation, to saying [K,S(a)] = 0. It will follow from the next theorem that if a system is periodic in a, it is also periodic in ka, where k is any iiteger.r Also, time-invariant systems are trivially periodic in the sense that the periodicity

98 condition is satisfied by all aER. We call periodic systems which are not time-invariant strictly periodic. In such cases an algebraic characterization discussed after the next theorem says that there is a minimum period which divides all other periods. Theorem 6.3.1 The following are equivalent (1) K is periodic with period a (2) S(a)S(a)K = S(a)KS(a) for some a s R (3) S(a)KS(a) = KS(a)S(a) for some a e R (4) S(a)S(a)K = S(a)KS(o) for all a E R (5) S(a)KS(a) = KS(a)S(a) for all a ~ R (6) S(po)K = KS(pa) for all p Z Proof: (1) => (2): trivially true for a = 0. (2) => (4): Let (2) be true for some aeR. Then (4) follows by successively pre-multiplying by S(-a) and S(B), where B is arbitrary in R. (3) => (5): Similar to above. (4) => (6): Let a = 0. When p = 0 the result is trivially true. An induction argument establishes (6) for non-negative p. The result for negative p follows from this by the obvious preand post-multiplications. (6) => (1): Let p = 1. It remains to show that (2) => (3) and (5) 4> (4). These, however, follow by suitable pre- and post-multiplications. At this point it is interesting to observe the following conclusions. Suppose l(T)K is continuous in T, and periodic K has periods which have.

9.9 some accumulation point in R. Then K is time-invariant. To see this, note that if a and v are two periods of K, a simple application of theorem 6.3.1 shows that la-vI is a period of K. Because the collection of periods accumulate, by this result arbitrarily small periods exist. SiJnce multiples of periods are periods, it is now clear that given any real number r there exist periods of K arbitrarily close to r. Hence, by continuity of l(T)K, *(r)K = 0. Since r was arbitrary this shows that K is time invariant. As an immediate corollary of this we have the statement that for systems with l(T)K continuous,.it is not possible for time-varying K to have a zero commutator over an interval of R, or equivalently, a system which has zero commutator over an interval of R is necessarily time-invariant. So, for systems which are smooth enough to have *(T)K continuous, we may re-define time-invariance as follows: A system K is time-invariant if {T:[S(T),K] = 0} has an accumulation point. In fact nothing quite as strong as continuity is required above. It is sufficient that P(T)K have no discontinuities of the second kind [R1]. It is the above statement which is the justification for experimental i-O verifications of time invariance in systems by observing that [S(T),K] = 0 for a large number of T's within some small interval of R. While a finite number of observations can never establish what is essentially a non-finite property, the above statement does provide a measure of condidence in such an experimental approach toward (partial) verification.

100 An interesting algebraic characterization of systems may be obtained in the foll owin;g way. Let lK =::[S(T),K] = 0} for a system K. Then IIK = {0} if and only ilfk is timne varying but not periodic. Next, observe that if a, B are pe-i.s of a periodic system K ka + ES is also a period of K, where k, ZeZ the set of integers. Thus IK is a Z-module. More can be said. 1nK:.ia cycleic nontrivial Z-module ifind only if.K is strictly periodic (i.e., periodic but not time-invariant). The positive generator of NK is then the period (meaning the smallest period) of K. In the forward'di-lt;iton-th^tirutt h of the imtplication is obvious. In the backward direc~tion it suffices tq show that if II is nontrivial and acyclic, then there is an accumulation into of tK. Let 661K and S # 0. Since 1K is K*.K K acyclic W.9l i: kiSkeZ, so there is a in 1K such that'K- k;< -i (k+l).8-'for:osome keZ. Thus O < a -k3< 6, and this shows that given arbitrary.3e,,.there exists yeSK such that 0 < y < 3, i.e. there is an accumulation point in [0,1]. These observations may be summarized by the following diagram K is trivial <=> K is time varying and non-periodic,K, system K, K is cyclic <=> K is strictly periodic r is nontrivial' ~-' ~ -K'. - -'.:;'is. acyclic'<=> K is time invariant K

101 Example 6.3.1 For the system K in example 6.2.3, [KS(2H1)x] = cost.x(t-2n1) [S(211)Kx] = cos (t-21)-x(t-211) = cost-x(t-21) so indeed KS(211) = S(211)K and it is easily seen that 211 is the minimal number for which the above is true. Hence the system is periodic with period 21. Similar reasoning will show that the system L in example 6.2.3 has period I More generally, given f a scalar-valued function, define K by (Kx)(t) = f(t)x(t) Then this system is periodic with period a if and only if f is periodic with period a. If we restrict consideration to a point in the input space X which is a constant function, the above system recaptures the classical function-theoretic meaning of periodicity, for in this case, say, XO(t) = 1, so (KXo)(t) = f(t)x(t) (KS(a)XO) (t)= (KX) (t)-f(t) (S(a)KXo)(t) = (S(a)f)(t) = f(t-ca) and indeed K is periodic if and only if f is periodic. Example 3.2 In the standard treatment of linear periodic systems the input-output description yields a K:C(-oo,oo) C(-_,) (Ku) (t) = f P (t)e ( )P(s)u(s)ds -_00 where P is a matrix periodic with period a, and R is a constant matrix. See, for example [P3]. The assumption here is that the system begins in

102 the O-state. Now, t [S(a)Ku](t) = P(t- a)e PfT- a)u( T-)dT 1, R(t-T) = P (t)eR tTP (T)U(T-ca)dT [KSo)u](t) = (t)e (t P(sas)u(s-a)ds ~COR(t-s) t p(tRet-s)p(s )u(s-o)ds = [S(a)Ku](t) thus vindicating the reasonableness of our definition. Beginning with this i-O definition of periodicity, assuming that a state system exists, it is conjectured that a Floquet-like state-'transition function must exist, and if so the definition is, in a sense, complete. Corollary 6.3.1 If K is periodic with period a then [K,S(T)] regarded as a system is periodic. Proof: By expanding S(a)[K,S(T)] and [K,S(T)]S(a) and appealing to conditions (4) and (5) of the theorem. (See the proof of the next lemma.) A partial converse to the above corollary is the next result. Corollary 6.3.2 If [K,S(T)] is periodic with period a then [K,S(a)] regarded as a

103 system is time-invariant. Proof: [K,S(T)] periodic with period a <=> S(a)KS(T) - S(a)S(T)K= KS(T)S(a) - S(T)KS(a) for all TER by theorem 6.3.1. Rearranging terms gives (SK(a) - S(a)K)S(T) = S(T)(KS(a) - SCa)K for all TcR. Since time-invariant operators form the 0 of the space [X > X]/C(X), in this quotient space the previous two corollaries would in fact be full converses if [K,S(T)] is independent of coset representative. That this is indeed so may be seen from the definition of +(T), but reiterated below for completeness. Let K,K2 be elements of the coset K+C(X). Then K1-K = C for some time-invariant C. Hence (K1-K2)S(T) - S(T)(K1-K2) = OVT, giving S(T) - S(T) = K2S(T) - S(T)K2VT, i.e., [K1,S(T)] = [K2S(T)]. The above argument also shows that within the same coset all elements have the same period, if any exists. This suggests the question: Does the set P(X) of all periodic systems form a linear subspace of [X + X]? For, if so, by the statement above on coset properties of periods, it follows that the partition on systems induced by C(X) must define that induced by P(X). That this is so is the substance of the next theorem, Theorem 6.3.2 P(X) is a subalgebra of [X + X], and [X X]/p is refined by [X -+ X]/C(X). Proof: If K,L are periodic with periods a and n, then it is easily shown that K+L and K*L are periodic with period the lowest common multiple of

104 a and n. JIt is clear that aK is periodic for any scalar a. {The above theorem is a purely algebraic statement. The corresponding topological statement cannot be made unless the space P(X) is closed under the operator norm topology. It turns out that P(X) is in fact not closed under the operator norm topology. However,i a -slightly weaker class of systems, which includes P(X), is indeed closed. To investigate this enlarged class an input-output characterization is given. Definition 6.3.2 A system K is called almost periodic if the following two conditions are satisfied: (1) For each c > 0 there exists a such that I S(o )K - KS(a<)ll<E (2) For each c > 0 there is,(e) > 0 such that every interval of length Z(E) contains a a satisfying the above inequality. ~ Following the terminology of almost periodic functions we call a a shift number. The theory of periodic and almost periodic systems- c.opeiy parallels that for scalar and Banach space valued periodic and almost periodic functions. The class of almost-periodic systems will be denoted by A(X). It is clear that P(X)cA(X). The difference between the above definition for almost periodicity and that for a scalar valued almost periodic function f is that condition (1) is, in the scalar function case, lf(t) - f(t+oa) <.

105 It turns out that K is almost periodic if and only if p(T)K is almost periodic as a scalar function. This is recorded later as:iScorollary 6.3.4. Precisely the same remarks may be made about recovering the classical meaning of almost-periodicity as were made about periodicity in the discussion following example 6.3.1. To explore some properties of P(X) and A(X) it will prove expedient to use the commutator and its norm. Theorem 6.3.3 If K is periodic (resp. almost periodic) then 4(T)K is periodic (resp. almost periodic) as a scalar function of T. Proof: When K is periodic the result follows from Corollary 6.3.1. To prove it for almost periodic K we have to exhibit, for each E > 0, a shift number o such that [I(T)K - I(T+o )Kj < e for all T. The demonstration of this is best separated out as the next lemma. Lemma 6.3.1 If I S(c)K - KS(a) II < E then I IS(a+T)K - KS(a)S(T)ll - I1S(T) - KS(T)II < for all. Proof: KS(T)S((a) - S(a)S(T)K =KS(T)S(a) - S(T)KS(o) + S(r)KS(a) - S(a)S(T)K So 0 l IlKS(T)S(a) - S(a)S(T)Kll < IIKS(T) - S(T)KI I 1S(a) 1 I + S(T) I l = IIKS(T) - S(T)K'Ill +,

106 Conversely, KS(T)S(a) - S(T)KS(a) = KS(T)S(o) - S(a)S(T)K + S(a)S(T)K S(T)KS(a) giving 0, I KS(T) -S(T)KII I KS(T)S(a) - S(a)S(T)KI I + and the two inequalities prove the result. It is evident that if P(T)K = 0 for some TO 0 then K is necessarily periodic, since the commutator [K,S(TO)] = 0 in this case. The simple converse of the Theorem 6.3.3 is clearly untrue since it is possible that i(T)K > 0 and yet is periodic, so K is not periodic. Thus a necessary and sufficient characterization for K to be periodic is that,p(T)K= 0 for some nonzero T. This is recorded as a corollary. Corollary 6.3.3 K is periodic if and only if *(T)K = 0 for some non-zero T. The situation for almost periodic systems is similar, but not quite as simple. Whenever l(T)K is almost periodic we have that given c > 0 there is ~(e) such that for every interval of length 9(c) there is a shift number a, i.e., for all T jI(T+c )K -,(T)Kj < e In particular, for T = 0 we have lS(a )K - KS(ao)l < showing that K is almost periodic. We state this result as: Corollary 6.3.4 K is almost periodic if and only if p(T)K is almost periodic. The condition analogous to that in Corollary 6.3.3 for this case

107 turns out to be not quite strong enough for sufficiency. This analogous condition is in fact Uim inf P('r)K = 0. It is Clearly a necessary condiT-0o tion for K to be almost periodic. For the sequel we shall need some results about almost periodic functions. These' are stated in the next lemma without proof in condensed form in terms of algebras. A good reference is Amerio [A5]. Lemma 6.3.1 The set of (continuous) almost periodic functions is a closed algebra. Remark: Continuity is an assumption which is really too strong for the truth of the above. If we consider almost periodic functions in the sense of Stepanov (see reference cited) then we may consider systems which are more general. However we defer this more complete development to a later report and concentrate here on more immediate issues. Lemma 6.3.2 The set B (X) of bounded systems for which ~(K) is continuous in T is a Banach subalgebra of [X + X]. Proof: First observe that [S(T), K+K] = [S(T),K] + [S(T),L] [S(T),KL] = [S(T),K].L + K [S(T),L] showing that this set is a subalgebra. That it is closed follows from the fact that uniform limits of continuous functions are continuous, and d) (K):RB - (X).

108 Theorem 6.3.4 The subset A (X) of almost periodic systems in B (X) is a Banach subalgebra. Proof: Let K, L be almost periodic. It is evident that aK is almost periodic. We wish to show K+L and K.L are almost periodic. By Corollary 6.3.4 it suffices to show that l(Tr)(K+L) and 9(T)(K'L) are almost periodic Also, by the same corollary and the hypotheses above, 9(T)K and ~(T)L are almost periodic. I S(T)(K+L) - (K+L)S(T)1I < IIS(T)K - KS(T) I + S(T)L - LS(T) I and the right hand side is a sum of two almost periodic functions, hence by lemma 6.3.1 is almost periodic; call it n. Observe that (O)(K+L) = 0 = n(0). Since r is almost periodic, for every ~ > 0 there is 2(e) such that for every interval of length (se) there is a shift number cr with In(a +T) - n(T) < e for all T. Choosing T = 0 we have the result IIS(ce)(K+L) - (K+L)S( )[] < e showing that K+L is almost periodic.. Next, observe that! IS(T)K L -,K.LS(T3)11 I IS(T)K- -KS(T)'II "IL, {+ I:K[I I S(T)L - LS(CT) I and the right hand side is almost periodic. A similar argument to the above says that K-L is almost periodic. Finally, suppose K +K, and K is almost periodic for every n. Then n11 n 0 I IS(T)Kn- KnS(T)l'IISC(T)K -KS()l I 1l Is(T)Kn - KnS(T)- S(T)K+ KS(t) I = IS(T) (KnK) + (K-Kn)S(T)II -^:2l iKhll^ -+O

109 So P(T)Kn + l(T)K. By corollary 6.3.4 P(T)K is almost periodic for each n, and so by lemma 6.3.1 P(T)K is almost periodic. Thus, using corollary 6.3.4 again, K is almost periodic. Corollary 6.3.5 Regarding A (X) as a closed linear subspace of B(X),B(X)/A (X) is a Banach space. It should be obvious that A (X) is not an ideal of B(X). 6.4 Homomorphisms Recall that a homomorphism from a system K:X + X to K1:X - X1 such that hK = Kh, and the system K1 may be regarded as a model of system K. Example 6.4.1 Let K:L2(-,oo) —) L2(-oo,o). Choose an orthonormal basis for L2(-oo,oo), calling it {e}. If K is linear, then the map h defined by n=l 00 k h: Ca e - C e n n n n n=l n=l yields a homomorphic system K1 which is also linear. K1 is K restricted k 1 to the subspace generated by {en} n=l n=l 00 More generally [B1] let {en}, be the nodes of a digraph. The n n=l branch a.. exists if and only if <ej,Kx> # 0 for some x such that 1J J. <ei,x> $ O. If the infinite matrix representation of this digraph is upper triangular except for an initial submatrix of finite dimension k,

110 then the h defined above is agian a homomorphism. K is not necessarily linear in this case, and the input-output space is any Hilbert space. The point here is that orthonormal bases may sometimes be chosen so that such a dependancy matrix is obtained. This emphasizes the fact that homomorphic simplification is a basis dependant procedure in practice. When applied to state systems homomorphisms go by the name aggregation [All] as discussed for the finite dimensional state case in chapter 4. The result presented in this section relates to the time-varying characteristics of systems which are homomorphic images of other systems. Given a homomorphism h:X + X1 of systems K:X + X and K:X -+ X1, the following arguments may be applied. It is first assumed that hS(T) S(T)h for all T, that is, h is time-invariant. This is the case for many homomorphisms schemes of importance, and is true in particular for the example above. Notationally, different S(T) should be used for the two sides of the equation because they act on different spaces, but where the context is clear we indulge in small liberties. Whenever h is linear it is easily shown that [S(T)K1 - K1S(T)]h = h[S(T)K-KS(T)] using Klh = hK and h time-invariant. This will be useful later in the chapter. Without this assumption, however, we have: Theorem 6.4.1 If K1 is a homomorphic image of K and h is time-invariant then K is time-invariant (resp. periodic) implies K1 is time-invariant (resp. periodic). Moreover, periods are preserved.

111 Proof: It suffices to show this for periodic K with period a. Because Klh = hK S(a)Klh - KhS(a) = S(a)hK - hKS(a) h[S(a)K - KS(a)] = 0 But K1 is periodic with period a if [S(a)K - K1S(a)]xl = 0 for all xl e X1 and since xl = hx for some xEX, this is true if S(a)Klh - klS(a)h = 0, i.e., if S(a)Klh - KlhS(a) = 0, which is the case. The converse inference problem is as usual much harder and requires additional assumptions. Without further assumptions, at least the following can be said. Suppose K1 is periodic. Let o be a period of K1. Then the range of S(a)K - KS(a) must be in the kernel of h. This means that the subset of X on which K is not periodic is "eliminated" by h in the passage to X1, a paraphrase of the fact that the choice of h in a modelling situation is partly to ignore portions of an input-output space which do not interest the modeller. Exactly the same remarks could be made about the time-invariance of K if K1 is time-invariant. Almost-periodicity, unlike time-invariance and periodicity, is not a purely algebraic concept. So the norms of the respective commutators have to be considered. In almost all cases of interest h is norm bounded, and this will be assumed. We turn our attention to the validity of homomorphisms with respect to almost-periodicity. Keeping the same notation, we have:

112 S(T)K| - KS(T)I = sup [S(T)K KS(T)lhxll xl o Ix ll I [jhlJ IIIS(T)K - KS(T)|I sup {IxlI IIS(T)K1- KS(T)ll < I hl I I IS()K - KS(r) I IM where M = sup inf_. xlwO xeh (xl) x ( Now, in cases where M is infinite, nothing can be said about the almost-periodicity of K1 when K is almost-periodic. In case M is finite, it is clear that K almost periodic implies K1 almost periodic. It turns out that M is indeed finite for many cases of interest, and in fact a reasonable homomorphism which attempts to capture, along with other properties, the time-varying property of K will probably yield an M which is finite (this is clearly not a necessary condition). In the example discussed at the beginning of this section, M is exactly 1. These conclusions are recorded as Theorem 6.4.2 If sup inf I xll' < then xl1O xch (x) Tixll K almost periodic => K1 almost periodic 1

113 Corollary 6.4.1 If h is a linear transformation from X to X1, X1 a subspace or a quotient space of X, then K almost periodic => K almost periodic. Analogous to the converse problem for periodicity, h acts such that for each ~ there'is "a a and. Ilh[S(o)K - KS(c )]xll < ~jxll whenever K is almost periodic. This inequality says that even if oa is not a shift number for K, h acts on the range of S(a )K - KS(c ) c 0 to eliminate the appearance of non almost periodicity in the passage to Xl. We digress a little at this point and consider linear systems and their adjoints. If K:X + X is a linear system, its adjoint is denoted by K*:X* X*, where X* is the dual space of X. When X is a Hilbert space X = X*, and then K and K* act on the same space. If K is linear and h is linear, K1 will be linear. Linearity will be assumed for the time being. Theorem 6.4.3 l(T)K = 4(T)K* for all. Proof: S(T)* = S(-T) is easily verified. The assertion above then follows from the fact that I IA*I I = I IAI for linear operator A, and [S(T)K - KS (T)]* = K*S(-T) - S T)K* Corollary 6.4.2 K is time-invariant (periodic, almost-periodic) if and only if K* is time-invariant (periodic, almost-periodic).

114 The relation of homomorphisms to adjoints is the following simple one. Theorem 6.4.4 If h is a linear homomorphism of K:X + X to K1:X1 + X1, then h* is a linear homomorphism of K*:X* + X1 to KIh X* X*. 1 1 1 h*(X*) Proof: Take the adjoint of hK = Klh. The nonsurjectivity of h* is clear fmom the simple case when X is finite dimensional, in which case dim(X*) = dim(X) > dim(X1) = dim(Xt) whenever h is not an isomorphism. The range of h* in X is a subspace X* on which K* is time-invariant (periodic) when K* is time-invariant (periodic), by theorem 6.4.1. For a system K the subset { {xeX:' (T)Kx = 0} is a subspace Y., T~R ibeing the intersection of kernels of linear operators, on which K has a time-invariant homomorphic image K, as the following example shows. Example 6.4.2 2 Let X be the linear space of functions from R to R and X be the linear space of functions from R to R. Let K be, defined' by (Kx)(t)l = 1/2 x(t)l + 1/2 x(t)2 + sint (Kx)(t)2 = 1/2 x(t)l + 1/2 x(t)2 - sint where the subscripts denote the projections onto that component. Then it is easily verified that h:R - R given by (hx)Itt) = x(t)1 + x(t)2 is a homomorphism of K to K1 = I the identity operator, which is time-invariant, but Y C R the time-invariant subspace of K is the trivial {0} - subspace.

Given K:X + X, and K*:X* + X*, denote the associated time-invariant subspaces by Y0 and Zo respectively, Y S X, Z. X*. A relation between Yo and Zo is the following. Ifx Y Yo, then for some T, [S(T)K - KS(T)]x 0. By the Hahn-Banach theorem there exists x!'X* such that <[S(T)K - KS(T)]x,x'> # 0 which is equivalent to <x,[K*S(-T)-S(-T)K*]x'> O. So x', Zo. Conversely, given x'; Zo, [K*S(-T) - S(-T)K*] x' 0 for some T. Then there is x 0 such that 0 <x,[K*S(-T) - S(-T)K*]x' = <[S(T)K - KS(T)]x,x'> so x K Y. 6.5 Higher order measures It was earlier observed that the measure of time-variance so far developed is not entirely adequate. Higher order measures can be introduced through Gateaux and Frechet derivatives of commutators [S(T),K] with respect to T. For a complete discussion of these derivatives in a normed linear space setting Kantorovich [K2] should be consulted. Here we recall some basic definitions and results relevant to our discussion. If K is an operator from X to Y, and X,Y are normed linear spaces, the Gateaux (G-) derivative of K at xo X is denoted by K^(xo), defined by K' ()x = lim K(x^+sx) - K(xo) 6+0 for each xeX. K' (xo) is a linear operator from X to Y. If the convergence above is uniform in X, the derivative is called the Frechet (F-) derivative of K at xo. The same symbol will be used for for both derivatives when the context is clear. If an F-derivative exists at xO, then K is said to be differentiable at x. If K happens to be linear, K is differentiable at every point x in X and K' (xo) = K. nth derivatives are denoted by superscript n. Suppose the G-derivative of K exists in some region of X. The derivative may be regarded as a map which associates each.point x in the region with a linear operator K'(x) from X to Y. Thus K':X + L(X,Y)

116 K has G-derivatives throughout X. If KT is continuous at xo, then K' (xo) is also an F-derivative. In the case when X is one-dimensional, so that we can identify X with the scalars, say R, it is a fact that L(R,Y) is isometrically isomorphic to Y. If LeL(R,Y), L(r) = rL(l), so every element in the range of L is a scalar multiple of L(1)eY. The mapping L + L(1) is evidently the isometric isomorphism sought. Thus we can identify L(RY) with Y. In particular, if P:R + Y is a (nonlinear) operator P':R + L(R,Y), so in fact P':R Y. The conclusion which is useful here is that if {Pa} is a collection of operators from R to Y which also contain their first derivatives, then {P)} must also contain all higher-order derivatives. Stated more succinctly, if {Pa} is closed under first derivatives then it is analytic, The P:R + Y above will take the form %(K):R + B(X) in our specialization, recalling that %(K)(t) = [K,S(T)]. Corresponding to i(T)K= II[K,S(T)]I, the quantity I [K,S(T)]nI or equivalently I 1(K)n(T) I will be denoted by 4 (T)K. If K,LEB(X) are such that 4(K) (T) and 4(L) (T) exist (either Gor F- derivatives), then %(K+aL) (T) exists for each scalar a. Therefore the subset of B(X) consisting of systems K for which ~(K) (T) exists is a linear subspace of B(X). In general this is not a closed subspace. An explicit form for ((K)n(T), the nth derivative of [K,S(T)], may be obtained. In fact it is easily verified that 4(K) (T) = [K,S(T)Dn] where D is the operator on X which yields time-derivatives of functions. D is a linear operator which is. clsed4 but not necessarily bounded unless it is onto and X is aEenachspace as a consequence of the closed graph theorem [T1-]). To render the subsequent discussion more tract able it will be assumed that X is a Banach space. -A simple instance of this is when X is the linear space of scalar-valued functions which

117 have bounded continuous derivatives up to the n-th order, and the norm is chosen to be the maximum of the sup-norms on each derivative. Actually, if X is not a Banach space, all that needs to be done is to replace norms by generalited norms in the discussion that follows. With the assumption, 9(K)n(T) is in B(X), so ~(K)n:R B (X). Lemma 6.5.1 n (T) is a seminorm on B(X), and is an even function in T. Proof: [K+aL,S(T)] = [K+aL,S(T)Dn] = [K,S(T)D ] + a[L,S(T)Dn] = [K,S(t)] a[L,S(T)]n from which the seminorm property is immediate. Evenness of in in T is a consequence of the time-invariance of D. Denote the set {K:' (T)K = 0} by D (T). This is a closed linear subspace of B(X). Closure follows from the equality [K,S(T)Dn] = (K-K )S(T)Dn + [KS(T)Dn] m m +S(T)Dn(K -K) for a sequence {K } in D (T) converging to K. m n This yields the result: Corollary 6.5.1'n(T) is a norm on B(X)/n (T). Paralleling the development for *(T) (1o(T) in the above notation), it is noted that the previous lemma and corollary may be extended to n [a,b] where in[a,b]K = sup in(T)K c T~[a,b] n whence n [a,b] is also a seminorm on B(X), and a norm on B(X)/Dn[a,b],

118 and is therefore closed. In particular, denote by in the map *n(-'o)' The map p discussed easlier corresponds to,'. Because of the assumption that X is a Banach space, D is bounded so [K,S(T)] = [K,S(T)Dn] is bounded. Further, II[K,S(T)Dn]Il < 211KII lIDnil showing that n is an ordinary seminorm for each n. Denoting the subspace (-~ o) simply by D it is clear that n is a norm on B(X)/D. n n n n' Lemma 6.5.2 As subspaces the collection {Vn} forms a chain 0 Do1'' n Proof: It suffices to show that if KMP then KED for arbitrary n. n n+l If KDc then [K,S(T)]n = 0 for all T and the derivative of the n 0 operator is 0. Corollary 6.5.2 The quotient spaces {B(X)/Pn} form a reverse chain B(X)/P0 2 B(X)/P1..... B (X)/V n...... Note that in the earlier notation C(X) corresponds to D0. A natural question arising from the foregoing is whether there is any simple way to combine the measures *n(T) and *n. We confine our remarks to in since they also apply to n (T) with the obvious modifications. The answer to this question is summarized in the next theorem. Theorem 6.5.1 Let n exist for n = 1,2,...k (possibly for all integers n).

119 The collection n generates a topology on B(X) with a base The con.l,...,k at 0 consisting of the family of all finite intersections rlV(il) n r2V(I2)... *frnV(P () r. > 0 n < k A 2'rn n>,:1 where V(in) = {K:-n(K) < 1}. With this topology, B(X) is a locally convex linear topological space. Proof: From the foregoing discussion n }n= is a collection of nn=l,..., - seminorms on B(X). The theorem is a standard result [Tl] in functi6nal analysis, given this fact. It is noted that if k < Q, the locally convex topology generated by fin \ is weaker than that generated by Vn}n ^^n=l,...,k' n=l,...9 If in exists for all integers n, and the locally convex topology generated by this family is considered, it is clearly weaker than the norm topology. (It would be interesting to discover under what circumstances it would be equal to the norm topology, but we do not pursue this matter.) Paraphrasing the last few results it may be said that each measure in successively refines the classification of systems according to successively higher orders of time-variance. Thus corollary 6.5.2 states th that this refinement proceeds in an orderly fashion, with the n order characteristics factored out before the (n+l)t. From the viewpoint of modelling it is the reverse of the refinement process that is relevant. A coset in B(X)/P is the form K+ P and consists of systems which n n are not distinguished insofar as (n+l)th order time-variance is neglected A canonical map from B(X)/P to B(X)/P coalesces two cosets K+P n n-_ n and L+V whenever nth order differences between K and L can be neglected. In the previous section it was shown that an i-O homomorphism h from system K to system K1, under certain conditions, preserved the 0-th order property of K in the passage to K1. Higher order properties,~ ~ ~ ihrodrpoete

120 will be investigated:here. I f h, is:time-invari int, linear and continuous, then. hD - h lim. S:(^6);- S(O) 6iS - *-limnh S(6) - S(O)& by.ntinui.ty 6+0 6 =^rn. S(6)h - S()h by time —invariaxace. and linearity: = lim S(6) -S(0) 6+0: 6 DhI Theomem: 6.5.2 If h is an i-0 homomorphism-which is linear, time:-invariant and n, n continuous, K? ='> D DnProf:i K~ED <=> KS(T)Kn = S (')D K The above remarks on,h are easily extended to show hD = Dnh Then K1S(T)Dnx1 = K1S(T)Dnhx, xeX = K1S (T)hDx n = KlhS(T) Dx n hKS(T)Dnx = hS(T)D Kx, KeDn1 = S(r) hKx = S(T)D Klhx so KlD. any B(X), th the sequene For any KsB(X), the elements of the sequence {t' (K)} may be zero

121 for some index m, in which case lemma 6.5.2 says n (K) = 0 for n > m. Call the least such m the index of K. In these terms the preceding theorem states that linear, continuous, time-invariant i-O homomorphisms cannot increase the index of systems. This statement generalizes the corresponding statement concerning o in the pervious section. In fact the proof of theorem 6.5.2 shows that under the assumptions about h, h[K,S(T)] = [K1,S(T)]nh This yields a generalization of theorem 6.4.2. Theorem 6.5. 3 If h is linear, continuous, time-invariant and satisfies M =sup inf Ilxll < X x 0. xEh-l(x1) I Ix I then II[K,S(T)]nll < M jhll Ij[K,S(T)]nl Proof: Using the equality h[K,S(T)] = [K1,S(T) h, mimic the proof of theorem 6.4.2. This result is paraphrased as saying that h maps a base of the n-induced seminorm topology on B(X) to the corresponding one on B(X). Thus if {K } is a sequence of operators converging in the locally n convex topology (of time-varying characteristics) to an operator K, the homomorphic image sequence {hK } must converge likewise to hK. That the converse is generally untrue is shown by example 6.4 the converse is generally untrue is shown by example. 6.4'.2.

122 This section is concluded with a few miscellaneous remarks. K. is timne"-invariant: if and only if it has. index zero:.. If K is peri-odic-then n(K is periodic for each n. To prove this; it is stufficient:to note that [K,S^(a)] = 0: impliKes S(')[K,S(T)] = [KS(a:T)]n. nn For linear, bounded K it is easy to verify that ([K,S{()] )* = [, hence n(K = n(K *) K for all n:. The: topology induced by the: 4 is not the only one that: is meaning:n.. ful for measuring time-varianc:e.. -Weighted integrals of the action of the:'n may serve the same function, and in some instances may prove to be more meaningful.. The.purpos:e ofi the -preceeding theory is to demonstrate that: such topologies are indeed.. avail.ab'le. 6.6 Discussion The bulk of this chapter consists of an attempt to make precise the fuzzy predicate of "siowly time varying'". It should be clear that this kind of fuzziness c:annot be removed easily by a strict numerical ordering, for if this is possib.le the he fuzziness would not have arisen in the first place. Our approach was to construct a topological measure of time-variance, thus essentially capturing the idea of a "distance" measure without really introducing a metric;. This was the content of theorem 6.5. 1. It was shown in theorem 6.4.1 that TIME-INV HOM(S, S' 3 (TIME —INV(S) TIME-INV(S' ) ) and TIME-INV_HOM(S,S-')': (PERIODIC(S) ~ PERIODIC (S')) We have no convenient name for'the condition placed on hbin the premise

123 of theorem 6.4.2. If we did, it is clear how the theorem could be written out as above, i.e., this instance of a homomorphism is ALMOST-PERIODIC valid. In particular Corollary 6.4.1 says that LINEAR SUBSPACE HOM(S,S) = (ALMOST-PERIODIC(S) v ALMOST-PERIODIC(S')) With higher order measures of time-variance these results are generalized so as to replace the predicates TIME-INV and PERIODIC by more sensitive predicates for which we do not as yet have appropriate names. The generalization to theorem 6.5.3 has special significance as indicated by the remarks following the theorem. Let us define a predicate CONVERGE such that CONVERGE ({S },S) <=> S converges to S in the topology for n n time-variance. which is an abbreviation of a second order formula of the type discussed in chapter 0. Then theorem 6.5.3 may be paraphrased to say that linear, continuous time-variant homomorphisms are CONVERGE-valid. Finally, looking at the index of systems as defined in the remarks following theorem 6.5.2, the same instance of a homomorphism was shown to be UB INDEX valid, where UB INDEX is a binary predicate such that UB INDEX(m,S) <=> m is an upper bound on the index of S.

Chapter 7 In this closing chapter we discuss a -few selected;open q5t:e:s motivated by the — r1eoing results. In imost instances of homonorphism schemes which were tested against systems-theoretic predicates, the particular instanti.aton igave sufficient conditions for validity wi'tlh:respect to those predicates.'It is not kno.wn hether a -complete charaterization of val id instances with Trespct to arbitrary sets of predicates is i possible. This correpsonds:to fidig necesisary Sand sufficient conditions for preservation of sys tem properTties:ad relations. It is c-onjectured that this is in general xot possible but I have not examined the question in detail. The noncomputability of system predicates for cnt:inuous systems.may be mitigated by considering:an analog theory of computability, as mentioned in Chapter 0. Developments in this direction could lead to new insights about continuous systems and their realizations. System realization theory for time-varying systems was not studied because a canonical realization theory is not available. If one relaxes the condition of canonicity, it should be possible to relate the i-O theory of Chapter 6 to a state-space theory, which will exhibit the time-varying characteristics induced by i-O functions and vice-versa. One predicate which was omitted is structural stability. Because this features very prominently in modern topological dynamics it is important that this be studied in the near future. It is anticipated that results in this area will contribute to atheory connecting local to global system homomorphisms. Structured homomorphisms [Z1] were not pursued in this investigation. Since much realistic modeling is performed with coordinatized sets it e124

125 would be desirable to develop a topological theory for such homomorphisms paralleling the preceding theory. Deeper results ought to be obtainable because of the much richer structure accompanying these homomorphisms. Finally, the whole issue of approximate and time-varying homomorphisms and stochastic systems is wide open. Convergence criteria should be established for approximate homomorphisms, and the relation between deterministic and nondeterministic systems via simplification procedures should be investigated. IThere are many classical problems in the approximation theory of systems which would benefit from being viewed in the perspective of predicate validity. Conversely, new procedures may in fact be suggested by this perspective.

REFERENCES (Al) Aoki.,M. "Control of Large Scale Dynamic Systems by:lAggregationl,'' IEEE Trans,. on- Automatic Control, Vol. AC-13, No 3.June- 1968. (A2) Ando, A.., Fisher,. F:. M., Simon, H.: A.- Essays on:thheStructure: of Social Science:. Models, MIT Press$. 19635. (A3): Arbib, MY A. "Decomposition Theory, for- Automatai ande Biotlogical Systems," JAC:, Aug. 1971, Systems- Structure- IEEE:Pu-i, No. 71 61. - CSS. (A4) _,'"Automata Theoy;-and: Cantrol Theory: A, Rapprochement-," Automatica, 5:3161 -1189, 1966. (AS) Aen^r:io L. AlHost-,-Periodic-: Functions and Functional Equations, Van- Nostrand-Relia-nholdj. 1971-.. (BI) Barto -,. A. G., Private? COmmunication, 1973. (B2). Balakrishnan, A. V. "State;- Space-. Theory of Linear-Time-Varying Systems,' in-: System-Thitory, ed. Zadeh- & Po-lak, McGraw-ill 1969-.(Dl)3 DeSantis, R. M. Causality! Structure of Engineerings Systems, Ph.D. Thesis, Computerr: Infrmation and Control Engineering, 1971, University of Michigan-. (D2) Damborg, M. and Naylor, A. "The-Fundamental Structure of InputOutput Stability for Feedback Systems," IEEE Trans. System Science and Cybernetics, Vo. SSC-6, No:. 2, April 1970. (D3) Day, J. M. "Semigroup-.Acts,,Algebraic, and Topological," Proceedings. of- the Second. Florida- Symposium on Automata and Semigroups, 1971,: Department. o:f.Mathematics, University of Florida, Gainsville, (D4) Dugundji, J. Topology,. Allyn G&Bacon, 1966. (Fl) Foo, N. "Topologizing State,-Construction" (Abstract),. Proceedings Seventh. PrincetonC- Conferenee.- onI Informationn Sciences- and Systems., March 1973. (F2) _, "Lattices,of:Homomorph-isms" (Abstract) Proceedings Eighth Princeton Conference, on:. Information.: Sciences and Systems., March 1974,..(Hl) Hartmanis J. and Stearns, R. Algebraic Structure Theory of Sequential Machines, Prentice, Hall, 1966. (K1) Kalman, R. E.:, Falb, P-. L., and.Arbib, M. A. Topics:in Mathematical System Theory, McGraw-Hill, 1969. (K2) Kantorovich, L. and Akilov, G. Functional Analysis in Normed Spaces, MacMillan, 1964:. ~ 126

127 (M1) Mihram, G. A. Simulation: Statistical Foundations and Methodology, Academic Press, 1972. (M2) __ "The Modeling Process," IEEE Trans. Systems, Man and Cybernetics, Vol. SMC-2, No. 5, Nov. 1972. (M3) Mesarovic, Macko & Takahara, Theory of Hierarchical, Multilevel Systems, Academic Press, 1970. (N1) Naylor, A. W. and Sell, G. Linear Operator Theory in Engineering and Science, Holt, Rinehart & Winstgn, 1971. (01) Onat, E.T. and Geary, J.A. "Representation of a class of nonlinear systems" Proceedings of the First International Symposium on Category Theory applied to Computation and Control, 1974; University of Massachusetts, Amherst. (P1) Park, D. J. M. "The Hierarchical Structure of Metabolic Networks and the Construction of Efficient Metabolic Simulators," To appear in the Journal of Theoretical Biology. (P2) Porter, W. A. and Zahm, C. L. Basic Concepts in System Theory, University of Michigan Technical Report 01656-2-T, Department of Electrical Engineering, 1969. (P3) Porter, W. A. Modern Foundations of'Systems Engineering, MacMillan, 1966. (P4) Pour-El, Marian B. "Abstract Computability versus Analoggenerability," Proceedings Cambridge Summer School in Logic, 1971, Springer-Verlag. (R1) Rudin, W. Principles of Mathematical Analysis, McGraw-Hill, 1964. (S1) Simon, H. A. "The Architecture of Complexity," Proceedings of the American Philosophical Society, 106:467-482, Dec. 1962. (S2) Saeks, R. "Causality in Hilbert Space," SIAM Review, Vol. 12, No. 3, July 1970. (S3) Sandberg, I. W. "Conditions for the Causality of Nonlinear Operators defined on a Linear Space," Quarterly of Applied Math., Vol. 23, No. 1, 1965. (T1) Taylor, A. E. Introduction to Functional Analysis, John Wiley, 1958. (W1) Wasow, W. R. Assymptotic Expansions for Ordinary Differential Equaions, Interscience, 1965. (W2) Willens, J. C. The Analysis of Feedback Systems, MIT Press, 1971. (Z1) Zeigler, B. P. "Towards a Formal Theory of Modeling and Simulation: Structure Preserving Morphisms,"> JACM, Vol. 19, No. 4, Oct. 1972.

128 (Z2), "Modeling and Simulation: Structure Preserving Morphisms for Discrete and Continuous Systems," Computers and Automata, Proceedings 21st International Conference, Polytechnic Institute of Brooklyn, N. Y., 1972. (3) __, "On the Formulation of Problems in Modeling and Simulation within the Framework of Mathematical Systems Theory," Proceedings Sixth International Congress on Cybernetics, Namur, Belgium, 1972. (Z4) Zeigler, B. P. and Weinberg, R. "System Theoretic Model Analysis: Computer Simulation of a Living Cell," J. Theoret. Biology, 29, 1970. (Z5) Zeigler, B. P. Theory of Modeling and Simulation, (Forthcoming Book) John Wiley, 1975. (Z6) Zadeh, L. A. "The Concepts of System, Aggregate, and State in System Theory," in System Theory, ed. Zadeh & Polak, McGraw-Hill, 1969. (Zal), "Fuzzy Sets," Information and Control, 8, 1965. UNIVERSITY OF MICHIGAN II 9IIIII 0II lU IIIl111 411111[ III 3 Gn5 02826 3443