THE U N I V E R S I T Y O F MI C H I G A N COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department THE HIERARCHY OF SYSTEM SPECIFICATIONS AND THE PROBLEM OF STRUCTURAL INFERENCE Bernard P. Zeigler The Logic of Computers Group and Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel June 1976 Technical Report No. 193 with assistance from: National Science Foundation Grant No. DCR71-01997 Washington, D.C.

THE HIERARCHY OF SYSTEM SPECIFICATIONS AND THE PROBLEM OF STRUCTURAL INFERENCE by Bernard P. Zeigler Department of Applied Mathematics, The Weizmann Institute of Science, Rehovot, Israel This work was partially supported by NSF Grant No. DCR71-01997, held by the Logic of Computers Group, University of Michigan, Ann Arbor, Michigan 48109, U.S.A, Presented at the Special Session on Recent Mathematical Developments of Relevance to Philosophy of Science, 1976 PSA Meeting, Chicago.

THE HIERARCHY OF SYSTEM SPECIFICATIONS AND THE PROBLEM OF STRUCTURAL INFERENCE 1. Introduction The activity of modelling proceeds by successive rounds of constructing abstract representations of reality and testing them against real world data. Since the testing is a comparison of behavior generated by the model with behavior observed for the modelled real system, it cannot directly validate the model structure, i.e. its claim as to how the real system works. This raises a central issue in modelling: is it possible to ascertain, even allowing aninfinite comparison of behavioral data, that a model truly represents the mechanism underlying a real behavior? To consider this issue, along with others of a similar fundamental nature, theories of modelling and simulation are being developed [1,2,3]. The author's theory consists of a set of postulates about the objects and activities involved in the modelling enterprise (a model of modelling) phrased within the theory of systems [4,5,6,7] and employs the tools of the latter to.consider such issues as the structural inference one mentioned above. The theory develops a hierarchy of levels of system specification:the lowest level providing for purely behavioral description, with each successive level introducing a standardized means of specifying more of the details of system structure. With any well defined object at level

i, it is possible to uniquely associate an object a level i-1. Thus through a series of steps, it is always possible to associate uniquely a behavior (lowest level description) with any structure. Morphisms (preservation relations) may be employed to relate objects at the same level. Objects so related have similar structure as viewed at the given level. Whenever a morphism runs between objects at level i, it induces a morphism at level i-1 to run between the associated objects at the lower level. The converse is not true. That is,one cannot in general infer that a level i morphism connects the level i specifications of two systems whose level i-1 specifications are related by a level i-1 morphism. There are however conditions, called justifying conditions, which justify the inference of higher level morphisms from lower level ones. In this paper we shall review the hierarchy in outline (more details are available in [1] and [8]). Then we shall show how the hierarchy enables consideration of the structural inference issue in a fundamental, rigorous manner. We shall proceed first with the outline of the system hierarchy (Fig. 1).

2. Levels of System Specifications Level O: Observation Frame An Observation Frame is a structure (T,X,Y) where T is a linearly ordered abelian group - the time base, X is a set - the input value set, Y is a set - the output value set. At this level we are able to set up experiments on the system by stimulating it over an interval of the time base T with values from X and observing its response of values from Y An input segment isa function w:<t,t >+X, where <t,t > is an...... 0 1 0 1 interval of T. (X,T) denotes the set of all input segments and similarly, (Y,T) is the set of all output segments. Level 1: I/O Relation Observation An Input/Output Relation Observation (IORO) is a structure (T,X,Q,,Y,R) where (T,X,Y) is an observation frame, Q is a set - the input segment set, R is a relation - the I/O relation,

with the constraints that a) c: (X,T) b) R c Qx(Y,T) where (w,p)ER - dom(w) = dom(p) At this level we have experimented on the system by applying input segments of the form w:<t,t >-*X and observing output segments of the 0 1 form p:<t,t >+Y; associated input-output segments (w,p) are observed 0 1 over the same interval [dom(w)=<t,t >=dom(p)]. We may restrict our 0 1 stimulus set to a subset Q of (X,T) Level 2: I/O Function Observation An I/O Function Observation (IOFO) is a structure (T,X,E,Y,F) where T, X, l, Y are as in Level 1 and F is a set of functions - the I/O functions with the constraint that fEF - f c Qx(Y,T) is a function such that dom(f(w))=dom(w). At this level we have knowledge of the "initial state" of the system,

in that if it is in a state represented by f then the input segment W will yield a unique response f(w) Level 3: I/O System An I/O System (S) is a structure <T,X,pQ,Q,Y,96,> where T, X, Q, Y are as in Level 1 Q is a set - the state set 6 is a function - the state transition function X is a function - the output function with the constraints that a) l is closed under composition of segments, b) 6 is a mapping from QxQ into Q which has the composition property 6(q,wL') = 6(6(q,w),w') for all contiguous pairs,',w'ER and their composition ww' (a segment which agrees with X on dom(w) and w' on dom(w') ). c) X is a mapping from Q to Y At this level we know the internal states of the system, Q. If the system is in state q and an input segment X is applied, it will be found in state 6(q,w) at the end of the experiment. The system

in state q is observed to produce X(q) as output. The composition property encodes the intuitive notion of the state as the sufficient record of past history to correctly predict future responses. Level 4: Network of Systems A Network of Systems (N) is a structure (T,X,,Q,Y,X,D, {S 1cED},{I acl D},{Z IaED}) where T, X, Q, Y are as in Level 3 D is a set - the index set designating components, Sa is a system - the component system I is a set - the set of immediate influencers of a, Z is a function - the connecting map for component a. Subject to the constraints: a) S = <T,X,l',Q,6 > b) I cD c) Z X Q xX X d) Z: X Qc Y E D. At this level we know,or specify,the system as a composition or network of component systems. Each component system receives input from a set of influencers (note that we have ommitted the output maps for the component systems since they can be encorporated into the connecting Z-maps).

3. Moving Down the Specification Hierarchy We now describe for each system specification at each level i>1 how to associate with it a unique specification at level i-l. By iterating this process we can associate a unique specification at level 1 with a level i specification (Fig. 2). Level transition 1+3 Given a network of systems N, we wish to associate with it a system SN which will be of the form (T,X,Q,,Y,6,x) where T, X, Q, Y, X come from the network structure and Q= X Q caED It remains to define 6. Given qEQ, mEQ, a state trajectory associated with q, w is a segment ~E(Q,T) such that D(t )=q and for each cED, for 0 tE<t,t >=dom(w) 0 1 6a(Pa(q),Za PI ) t - t>) Pa(t) [Here P projects Q onto a P1 projects Q onto X Q t> =l'<t,t > and Z.PI ot,(t'): Z (PI( t>(t' ))) *] Thus a state trajectory is defined implicitly as a motion through Q space which is such that when it is projected through each Za-map as input

to the component system a, the resulting state trajectory through Qa is precisely the projection of the motion on a We say that N has unique trajectories if for each qEQ and uE, there is exactly one associated trajectory, call it 0q. In this case, we have a well defined 6:Qx?+~Q, namely 6(q,w)=:q (t ). It can be q,w 1 readily verified that 6 has the composition property. Level transition 3+2 Given a system S=<T,X,IQ,Q,Y,6,X>. We associate with it an IOFO (T,X,Q,Y,F) where F={'qlqeQ}, where the I/O function i5':Q + (Y,T) is defined by 'fq(w)(t) =q(wt>)=x(6( ) for tEdomt>) Level transition 2+1 Given an IOFO (T,X,Q,Y,F) we associate with it an IORO (T,X,Q,Y,R) where R= U f fEF 4. Hierarchy of Morphisms We consider the morphisms appropriate to the levels of the specification hierarchy. Level 1: I/O Relation Morphism An I/O relation morphism from (T,X,Q,Y,R) to (T',X',j',Y',R') is

a pair (g,k) such that g:Q'-gQ, k:(Y,T) onto (Y',T') and for every (w',p')ER', there is a pair (w,p)ER such that g(w)=w' and k(p)=p' Thus suppose p' is produced in response to w' in the small system (primed). Encoding w' as an input segment g(w') for the big system we find an associated response p which is decoded via k to p'. As a special case when k and g are identities, we have R' c R Level 2: I/O Function Morphism An I/O Function Morphism from (T,X,Q,Y,F) to (T',X',E2',Y',F') is a pair (g,k) such that g:Q'-*Q, k:(Y,T) ont9 (Y',T'), and for each f'EF', there is an fEF such that f'=k-f g Thus each initial state function of the small system is "simulatable" by some such function of the big system using the same encoding-decoding pair (g,k). As a special case, when g and k are identity mappings, we have F' c F Level 3: System Morphism A System Morphism from S to S' is a triple (g,h,Y() such that g:-'-Q, h:Q ont_ Q' where Q c Q, J(:Y ontq Y', and for each qEQ, m'EQ', we have h.6(q,g(w'))=6'(h(q),w') (transition function preservation) and (.X(q)=X'-h(q) (output function preservation). Thus, pairs of states which correspond under the mapping h transit under related segments to pairs of state which are again related by h The outputs observed from related states correspond under the mapping.k

10 In a system morphism (g,h,$) in which g and, are identities, and Q=Q h is called a homorphism. Level 4: Network Morphism We shall restrict our attention to networks N and N' with the same component index set D. A Network Morphism from N to N' is a structure (g,{m latED},V) where for each aED a) m (g,h) is a system morphism from S to S' (local transition function preservation). b) With h= X h.P,we require that for each state trajectory 4,ED a of N and each wEQ' such that dom(w)=dom(4) Z (Pi.,g(w)) = g.ZP,(Pi.h-*D,w) (preservation of connecting maps). c) I, c I (preservation of influencers), and in addition d) K-X=X'h. The network morphism expresses a component-by-component simulation. It requires that each big component system Su simulate small component system S', that each big connecting map ZO simulate small connecting map Z', and that the network connection structure be preserved in the sense that if small system S' influences small system S', then big system Sg also influences big system S.

11 5. Moving Down the Morphism Hierarchy Analogously to the descent through the specification hierarchy, we show how to associate a unique morphism at level i-1 given a morphism at level i for i>1. By iterating this process we can associate a unique morphism at level 1 with a level i morphism (Fig. 2). Transition 4+3 Given networks N and N', let SN and SN, be the associated systems (assuming unique trajectories). If (g,{mnlcED},]() is a network morphism from N to N', then (g,h,)) is a system morphism from SN to SN' where h= X h.P aED c o The proof shows that h* g(=hq It then follows that q,g(w( h(q),w h(6(q,g(w))=h qg()t )=-(q),w (t )=:'(h(q),w), as required. Transition 3-+2 Given systems S and S' let IOFOs and IOFOS, be the associated I/O function observations. Let (g,h,y) be a system morphism from S to S' such that g is invertable, i.e. g preserves left segmentation [g(mt>)=g(w)t>] and g is one-one on domains [dom(w)=dom(w')>dom(g(w)) =dom(g(w'))]. Then (g,k) is an I/O function morphism from S to S' where k:(Y,T) on__ (Y',T') is defined such that if dom(p)=dom(g(w)) =<t,t >, then k(p)(t')=:(p(t )) where dom K(p)=dom(w)=<t',t'>. 0 I 1 1 0 1 The proof checks that k.~I~ * i.e., that each initial state k-q-g:~h(q) '

function q, of the small system is simulated by at least one initial q state function 'q of the big system, where qEh1-(q') Transition 2-1 Given I/O function observations IOFO and IOFO', let IORO and IORO' be the associated I/O relation observations. Then if (g,k) is an I/O function morphism from IOFO to IOFO', then (g,h) is also an I/O relation morphism from IORO to IORO'. The proof is straightforward. 6. Climbing Up the Hierarchy The problem is phraseable as follows: given any pair of systems specified at level i+1 whose associated specifications at level i are related by a level i morphism, under what conditions, can we infer that a level i+1 morphism connects the level i+1 specifications? These conditions are called justifying conditions, and should be shown to be necessary for making the inference, in the sense that, by deleting any one of the component conditions, there can be shown to be counter examples to the inference. The problem of finding justifying conditions is a difficult one, and only a number of special cases are well understood. We shall restrict ourselves to some of these cases in the follbwing.

13 Level transition 1+2 Let S and S' be systems specified at Level 3, and let S and S' share the same observation frame (T,X,Y). For the associated level 1 specifications IORO =(T,X,Q',Y',R') and IOROs=(T,X,Q,Y,R), let R'=R, this is a special case of an I/O relation morphism from IORO to IORO'. Let IOFOs,=(T,X,Q',Y,F') and IOFOs=(T,X,Q,Y,F) be the associated Level 2 specifications. A justifying condition for the inference F' c F (a special case of the I/O function morphism) is that S' be identifiable i.e. for every state q'EQ', there is an I/O pair (w,p) which identifies q' in the sense that q' is the only state possible for S' to be in at the end of any experiment in which w is applied and p is observed. The proof that this condition works, its minimality, and equivalent rephrasings are given in [1]. Intuitively, by knowing that (w,p) identifies a state (which is itself unknown) we can attribute all pairs (m,p) to that state, for which (wx,pp) is an I/O pair in R'=R. The pairs (ap) necessarily constitute an I/O function which is found in both F' and in F (it may appear more than once in F, since S was not assumed to be identifiable). Level transition 2+3 Let S and S' be systems specified at Level 3, and let S and S' share the same observation frame (T,X,Y). For the associated Level 2 specifications, IOFOs,=(T,X,Q',Y,F') and IOFOs=(T,X,Q,Y,F), let F' c F

(special case of an I/O function morphism from IOFOs to IOFOs,). Then a justifying condition for the inference "S' is a homomorphic image of a subsystem of S" is that S' be reduced, i.e. that is that distinct states of S' have distinct I/O functions (equivalently, for every pair of states q, q', there is a input segment w for which the responses p, p' are different). The proof, as well as the generalization to arbitrary I/O function morphisms, is given in [1]. The proof relies on the fact that states which are equivalent (have the same I/O function) are sent to equivalent states under all input segments. This enables a mapping to be defined which maps equivalent states of the big system S to their unique (by S' being reduced) representative in little system S' Level transition 3+4 Given networks N and N' let SN and SN, be the associated systems specified at Level 3. Given that a system (Level 3) morphism runs from SN to SNI, we seek justifying conditions for inferring that a network (Level 4) morphism runs from N to N'. This is the problem of uniquely identifying the local component systems and their interaction for a system whose global transition behavior is known. This is the most interesting of the structural inference problems and also the one for which least is known of general nature. Examination of the special case of discrete time systems was initiated in [9] where justifying conditions based upon"irredundant"sets and "location preservation" were given. Recently, significant advances have been made in characterizing the irredundance and location preservation properties, and

in employing these ideas as a basis for a computer aided methodology of model structure identification [10]. 7. Application of the Hierarchy to Knowledge Aquisition and Structural Inference We now phrase the structural inference problem within the language of systems just reviewed. The modeller, as experimenter, sets up an Observation Frame at Level O and proceeds to collect data, which being composed of input/output observations, places the data gathering activity in Level 1. We assert that Level 1 is also the only level at which direct knowledge about the real system can be acquired. By having knowledge at level i, we mean that the modeller is able to point to a unique system specification at level i whose associated Level 1 specification is that of the acquired IORO at Level 1. Thus for example a modeller knows the network structure of the real system if he can establish that there is only one system specification at Level 4 whose associated input/output relation is that actually acquired at Level 1. Of course to make any sense, the uniqueness must be construed as up to an appropriate equivalence. The structural inference problem then relates to the possibility and the practicality, of inferring a unique higher level specification from a lower level one, or more colloqn'ally, of acquiring higher level knowledge. In [8] we distinguished three methodologies for knowledge acquisition.

16 The discovery approach attempts to climb up the knowledge hierarchy driven by observational (Level 1) data alone. The postulational approach postulates higher level models for validation at the observational Level 1. The combined approach employs the discovery approach to suggest models to try, when a "better" basis (such as intuition or physical laws) for postulating models is not available. In all of these approaches one ultimately winds up with the following situation: Let S. be the system specification at level i which the modeller takes to be known. (At the beginning i=1, and the acquired IORO is the firm knowledge assumed.) Let Ci+1 be the set of all specifications at level i+1 whose associated specification at level i is Si, and let ScECi+l be the modeller's current candidate for validity at level i+1, (Fig. 4).(In the discovery approach this might be the level i+1 specification derived from the level i knowledge by the given data processing procedure; in the postulational approach, this might be the level i+1 specification representing the modeller's hypothesis about how the real system works). The structural inference problem is then phraseable as: under what conditions is Sc unique, in the sense that it is a level i+1 morphic image of every S in Ci+1? Intuitively, when is Sc, as a valid explanation, a part of every other valid explanation? The answer is given by the justifying conditions for the level i to i+1 transition. Reason: every SECi+1 and Sc have identical (hence morphically related) associated specifications at level i. If the justifying conditions are satisfied with Sc in the role of S',then there is

17 a level i+1 morphism from S to Sc. If the justifying conditions refer only to Sc,then the modeller can check his candidate to see if the conditions are satisfied (and/or to construct his model so that they are satisfied). This is the case for transitions 1+2 and 2+3. If as in the case 3+4, the conditions involve both S' and S, the modeller must restrict his assertion of uniqueness to the subset of C+1, which satisfy the conditions. Two comments: The question of whether there are specifications Sc in Ci+1 which do in fact satisfy the justifying conditions, and how to construct them in principle, is a purely mathematical problem. Such specifications are called cannonical realizations and have been much studied at the level 2+3 transition [1,5,7]. The structural inference problem can be extended to allow for the effect of future additionstoc rent knowledge (Fig. 4b). Thus if Si represents the current knowledge at level i, then Ei, the set of all level i specifications for which Si is a level i morphic image, represents all possible extensions of current knowledge which do not contradict it. At Level 1, E includes for example the set of I/O relations which include the currently acquired I/O pairs. Now let Ci+1 be the set of specifications at level i+1 whose associated specifications at level i belong to E. Let S cECi+ be the modeller's candidate for validity at level i+1, and let S be any other element of Ci+l. Then Sc is a level i+1 morphic image of S if the justifying conditions hold for Sc and S. Naturally, the finding of justifying conditions is much harder for the

extended version of structural problem. The theory of [1,8] postulates five elements as basic to the modelling enterprise - real system, experimental frame, base model, lumped model and computer. The base model is presented as being postulated, once and for all, and represents a set of models, all sharing some structure at Level 4, (what the modeller takes as known at a given time) and differing in other structural features at Level 4 (what is unknown at a given time). The analysis of structural inference we have just given however, shows that a fixed base model is not strictly necessary, and can be replaced by a more general notion, in which the modeller justifies his inferences with respect to abstract subsets of the form Ci+1 above. It is doubtful however, whether humans can operate effectively without visualizing a particular base model as giving rise via simplification to the current lumped model under test. What may happen however is that the modeller may change his base model as he leatns more about the real system. Two things may then happen: The new base model will be equivalent to the old one in the sense of both satisfying or both not satisfying the justifying conditions. This may happen for example if the new base model refines, but does not restructure, the old one. In this case, the status of the knowledge infered for the base model does not change. If however, the new base model is not equivalent (in the above sense) to the old, then the status may be radically altered, for the worse (if old inferences can no longer be justified) or for the better (if inferences which could not previously be made are now justifiable ). Could such happenings be the stuff of Kuhn's (11) scientific revolutions?

References 1. B.P.Zeigler, Theory of Modelling and Simulation, Wiley and Sons, New York, 1976. 2. G.C. Corynen, A Mathematical Theory of Modelling and Simulation, Ph.D. Dissertation, University of Michigan, 1975. 3. J. Jaron, "Functionisms and Morphisms of Complex Cybernetical Systems", Cybernetica, 15, 1972, 26-38. 4. G.J. Klir, An Approach to General Systems Theory, Von Nostrand Reinhold, New York, 1969. 5. L. Padulo and M.A. Arbib, Systems Theory, Saunders, Philadelphia, Pa., 1974. 6. A.W. Wymore, A Mathematical Theory of Systems Engineering: The Elements, Wiley and Sons, New York, 1967. 7: M.D. Mesaroic and Y. Takahara, Foundations for a Mathematical Systems Theory, Academic Press, New York, 1974. 8. BP.Zeigler, "A Conceptual Basis For Modelling and Simulation", Int. Jnl. Gen. Sys., 1, 1974, pp. 213-228. 9. B.P.Zeigler, "Towards a Formal Theory of Modelling and Simulation: Structure Preserving Morphisms" J.A.C.M., 19, 1972, pp. 742 -764.

20 10. A. Zalecka-Melamed, The Inference of Network Structure for Discrete Time Systems, Ph.D. Dissertation, The University of Michigan, 1976. 11. T. Kuhn, The Structure of Scientific Revolutions, University of Chicago Press, Chicago, 1962.

21 Level 0 Observation Frame <T,X,Y> Level 1 I/O Relation Observation <T,X,Q,Y,R> Level 2 I/O Function Observation <T,X,Q,Y,F> Level 3 I/O System <T,X,2,Q,Y,6,X> Level 4 Network of Systems <T,X,Q,Y,X,D,{S },{I },{Z }> Figure 1: Levels of System Specifications (9,() Level 1 IORO -~ IOROs N N' + (g,() + Level 2 IOFO i IOFO N N' + (gh=xh,,) + Level 3 SN SN + (g,{ },~) + Level 4 N a N' Figure 2: Moving Down the Hierarchy Level 1 IORO + IORO' + 1 + Level 2 IOFO - ~+ V1 justifying conditions Level 3 S — S ~ 1o Level 4 N - N' Figure 3: Climbing up the Hierarchy

3 9015 03527 6248 Si Level i i association Level i+l Ci+ ( morphism (a) morphism Level i -- Six association Levelil i+ Sc /f Ci+l (b) Figure 4. Structural inference