ABSTRACT STRUCTURAL REALIZATIONS OF PROGRAM SCHEMATA BY John G. Miles Finite state machine theory can be employed to synthesize and detect common program structures ("con- trols" or "schemata”) when these can be identified as sequential machines. The computation a program per- forms can be described as an interpretation or mapping on these structures. This dissertation proposes a program model and deyeIOps a number of structural real- izations for common controls. The necessary construc- tions of appropriate interpretations on those controls to preserve program equivalence are described. A par- ticular set of machine transformations is introduced which can be used to design Optimal common control realizations. STRUCTURAL REALIZATIONS OF PROGRAM SCHEMATA BY John G. Miles A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Computer Science 1971 To Hall John Miles and Arline Miles ACKNOWLEDGEMENTS I wish to thank Professors Robert Barr, Richard Dubes, Julian Kateley and William Kilmer for serving on my doctorol committee and for many inspiring class- room sessions. I am especially grateful to my commit- tee chairman, Dr. Carl Page, for his patient and sym- pathetic help in developing the ideas of this work. I am deeply indebted to Dr. Richard Reid for the many opportunities made available to me while at MSU. Also, I would like to thank the Division of Engineering Research, under the able hand of John Hoffman, which provided both financial assistance and intellectual nurture during my graduate studies. The price extracted for the completion of this venture would not have been met without the understand- ing, loyality and patience of my wife, Vicki. Finally, my sincere thanks to Dr. Martin Keeney, whose friendship and encouragement in large measure sus- tained my efforts throughout my education. TABLE OF CONTENTS ACKNOWLEDGEMENTS LIST OF FIGURES LIST OF SYMBOLS AND TERMS Chapter I. II. III. IV. PROGRAM SPECIFICATION AND MODEL 1.1 Introduction 1.2 Dissertation Objectives 1.3 'Algorithm Specifications 1.4 Program Model 1.5 Mathematical Preliminaries CONTROL EQUIVALENCE AND STRUCTURAL REALIZABILITY 2.1 Program Value and Valuation Sequences 2.2 Program and Control Equivalence 2.3 Structural Realizability of Control SYNTHESIZING PROGRAMS WITH COMMON CONTROLS 3.1 SP Partition Realizations 3.2 Semigroup Realizations 3.3 Example of Semigroup Control Realization 3.4 Composite Realizations MINIMUM STRUCTURAL REALIZATIONS 4.1 Subdirect Product Realizations 4.2 Value Equivalent Control Transformations 4.3 SubOptimal SP Partitions, Semigroup and Composite Realizations 4.4 Suboptimal Direct Product Realizations ii Page iv vi CDNU'IMI—‘H‘ t—‘H 33 46 51 72 73 8O 83 99 119 119 134 140 157 TABLE OF CONTENTS (Cont'd.) Page Chapter V. CONCLUSIONS AND OPEN PROBLEMS 184 5.1 Summary 184 5.2 Conclusions 186 5.3 Open Questions 187 BIBLIOGRAPHY 191 iii 2.4 3-1 (a).(b) 3.2 (a).(b) (C).(d).(e) 3-3 (a).(b) 3.4 3.5 3.6 3.7 3.8 (a).(b) 3.9 LIST OF FIGURES Two State Control, T An A-type Realization of T Flow Chart for I[r] Flow Chart for IA[T] Interpreted Controls $1 and 02 f and the SP Lattice, L? Interpretations on F to Simulate fl and fl 1 2 Flow Chart of 0 Start State Configurations State Diagram of Semigroup Accumulator F F Control Flow Chart Flow Charts of TI, 02 Controls T1, T2 S-State Equivalent Control for 12 Minimum Grids, G , G T1 T2 Multiple Minimum Grids 5-State Equivalent Machine in L5[r] iv Page 58 58 62 62 77 78 78 86 89 91 94, 95 101, 103 105 109 110 113 102 Figure 4.2 4-3 (a) .(b) 4.4 (a) ,(b) 4.5 4.6 4.7 4.8 (a).(b) LIST OF FIGURES (Cont'd.) 4th Order Runga-Kutta Formulation of the Differential Equation y = f(t.y) Newton-Raphson Scheme for Solution to Nonlinear Equation F(x) = 0 Controls for Runga-Kutta and Newton-Raphson Programs I 1’T 2 Direct Product of Transformed Controls Transformed Controls r’ State Homomorphisms of F onto T1 and 12 f and the Reorderings 1? i = 0,7 FSM Control and its Combinatorial Semigroup Page 126 128 130 131 I32 133 142, 155 143 M“) 40) LIST OF SYMBOLS AND TERMS Algorithm represented by a finite state machine Set of all finite input sequences on an alphabet, Z, 7. Completely specified I/O function for a FSM,7. Denotes "correspdnds to" 1 Logical implication Set membership I/O function formed by left translation, 7. ith input symbol of a finite input alphabet Finite length tapes Computer representation, 14. Location index set of computer memory, 14. Also a finite state machine depending on context. Base set, 15. State set of C, 15. All functions on D, 15. Set of finitely composed functions from F. Set of all finite decision predicates on D, 16. 1th K-ary decision predicate on D, 7, 16. Program schema or control, 16. A tuple denoting an algebraic structure State transition function, 16. Output function, 16. Interpretation on a control, 16. vi LIST OF SYMBOLS AND TERMS (Cont'd.) nC.) Map from control states to a computation sequence and decision predicate, 17. y(-) Map from states to decision predicates, 17. c(-) Map from output set to computation sequence, 17. d,d0 An initial state of D, 17. I[r] Interpreted schema or program, 17. A,Y Used variously to denote a finite set of output symbols for a FSM, 16, 18. w(-) Assignment map for machine realization, 19. a(-) State to state subsets map, 19. p(-) Input to input alphabet map, 19. §(-) Output to output map, 19. A-type Denotes a particular machine realization, 20. ¢(.) Machine or control homomorphism, 20. hl(.) State to State map of the homomorphism, 20. h2(') égput to input alphabet map of the homomorphism, h3(-) Output to output map of the homomorphism, 20. M ,r Machine or control assignment restriction, 21. w w H-type ggnotes a particular type of machine realization, 4* Machine capability, 22. p* Input alphabet to Input string map, 22. vii LIST OF SYMBOLS AND TERMS (Cont'd.) R A binary relation with varying attributes depending on context. ‘ SP Denotes an SP partition, 23. LM,LT SP lattices of a machine or control, 24. M,nT An SP partition of a machine or control, 24. SM,Sr Semigroup accumulator of a machine or control, 28. Also the state set of a machine or control depending on context. M X M2, The direct product of two machines or controls, ~ 28. i C [M x M , Connected direct product machine or control, 29. WC TXT [12, QT The state set of a control. (Q1XQ2)r Reachable set of states in a direct product machine or control, 29. g Isomorphism. rpM(-) Response function of a machine or control, 31. rpT(-) rpS (°) Alternate designation of the response function 0 with emphasis on the initial state. Cyclic T A control whose states are all reachable from a single start state, 31. 9 Program [= I[r]] on an interpretated control, 33. viii Common Control, LIST OF SYMBOLS AND TERMS (Cont'd.) I” The value of a program, 33. The valuation sequence on 2, 34. Initial configuration-free program, 34, 35. Set of all valuation sequences for T, 35. Set of all program values for T, 35. Program value equivalence, 48. Interpretation equivalence relation on controls, 49, Control equivalence class under E, 49. I Interpretation equivalence relation on control equivalence classes, 49. Common control for a class of controls, 50. RI relation between two controls, one of which is an A-type realization of the other, 52. A-type interpretation construction, 54. RI relation between two controls, one of which is an H-type realization of the other, 63. Output-free control, or semi-control, 73. Submachine of r induced by SP partition, 0, on Of, 74. Set of minimum grids, 108. A member of Of, 108. Set of m-state labeled extension of T, 110. ix 7% LIST OF SYMBOLS AND TERMS (Cont'd.) Exit states, 117. Modified decision predicate due to a reorder- ing transformation, 133. ith reordering of the state transitions of the control, T, 134. Base ten representation of the number n. (n)2 +9 base two, 134. State transition function of the reordered control, 11, 134. Class of all FSM semi-controls with n states over a binary alphabet, 146. A subset of T, each member of the set having at least one n-k+1 block SP partition, 146. Set of reachable states from state q by tapes * SP state cover, 157. Set of R-minimal direct product controls, 158. The ?2 induced cover on T1 for the direct pro- duct, 11x12, 158. The sum of all elements in blocks of the cover, 0 , 161. 1‘ State set generated by the reordering technique in Theorem 4.12, 177. End of proof symbol. CHAPTER I PROGRAM SPECIFICATIONS AND MODEL 1.1 Introduction In recent years some notions of a general theory of computability have begun to take shape in the hands of an increasing number of researchers. The breadth of the field is as extensive as the number of people working on topics ranging from formal language theory, to Turing machines and recursive function theory. The overall objectives are iden- tical: What is a computation and is there a convenient model to describe how man and machine work together to ac- complish it? The formalisms introduced are useful for studying powerful global aspects in these areas but are of little value to someone trying to program an algorithm, or finite process, in some programming language. This dissertation will describe and investigate cer- tain aspects in the process of programming an algorithm from its inception to a final implementation in some prob- lem oriented language. The goal throughout will be to model and organize programs independent of any particular computer and programming language thus establishing a basis for "engineering" large systems programs. A mathematical model will be used to investigate certain properties of prOgrams such as one program's ability to simulate another, program equivalence, and program value (i.e. the set of computations performed). Primarily, the structure of pro- grams defined by the model will be studied for possible inferences on these properties. The ensuing discussion is particularly relevant in the treatment of algorithms which perform some kind of numerical computation. Simulation studies and engineering design and analysis methods rely heavily on such common- place algorithms as root-finding and solution of simultaneous linear and nonlinear differential equations. The fact that the number of algorithms in this category is so vast and that most large programs used by engineers in analysis and design employ dozens of such schemes requires some means of systematically developing these programs, keeping them updated and monitoring their performance. It will be worthwhile if the identification and organization of primary aspects in the programming process contained herein leads to a more methodical approach in the design of such large programs. 1.2 Dissertation Objectives The basic premise of this dissertation is that finite state machine (or automata) theory has considerable poten- tial in dealing with the practical problems of program design. Structure and effect of programs, and information structures in general, can be thought of in terms of the structure and behavior of a finite state machine (FSM). From the standpoint of finite state machine theory, generating structurally related controls or program sche- mata usually guarantees behavioral equivalence. A direct parallel could be drawn to program behavioral equivalence were it not for severe implementation problems arising as a result of different structural relationships. These difficulties are quite apart from FSM theoretic consider- ations. But to take advantage of the wealth of FSM theory, an intuitively appropriate model of a program and notions of program and control equivalence must be defined so as to create an environment where practical programming pro- blems can be dealt with in terms of FSM concepts. In this dissertation such a program model is defined and used to construct structurally equivalent--hence value equivalent-- programs. In addition, procedures will be introduced and employed in the optimization of such programs. Of major importance throughout the development of these matters is the exposition of implementation difficulties and the conditions under which they occur. Whenever possible, proofs have been designed to be constructive in reveal- ing these problems. Section 1.3 introduces the notion of an algorithm and its realization as a finite state machine from an initial specification. This sets the stage for a pre- sentation of a complete program model in Section 1.4. The material in Chapters 11, III, and IV relies heavily on FSM concepts reviewed in Section 1.5, especially the classic notions of machine realizability. Contained in the first section of Chapter II are definitions of program value and valuation sequences along with necessary and sufficient conditions relating valuation sequences and program values in a one to one manner. A program value equivalence relation is defined in the next section and leads to a partial ordering on program schemata and the notion of a common control for a class of program schemata. In Section 2.3 structural realization theorems are presented which Show how appro- priate interpretations are constructed to preserve program value. I: ‘1 '1 ‘v ‘0 ~\. Chapter III is concerned with the synthesis of three common controls of a particular structural type. Two realizations, S.P. partition (Section 3.1) and semi- group (Section 3.2) realizations, involve concepts which are not new. The composite realization (Section 3.4) is a deceptively simple model of what is an intuitively appealing, and quite direct, approach to constructing common controls. Section 3.3 contains a complete example of a practical use of semigroup common controls. A fourth common control realization, utilizing direct products, is developed in the first section of Chapter IV. Section 4.2 introduces a new class of machine transfor- mations. It is shown that while structural equivalence is not preserved under these transformations, program value i§_when the appropriate interpretations are con- structed. Sections 4.3 and 4.4 investigate the use of these transformations in synthesizing Optimal common con- trols of the type studied in previous sections. 1.3 Algorithm Specification To model any physical device which is to interact with a given environment in some predetermined way, it is essential to specify the function and nature of the cu. .o- I .’A ‘I- 4.... n, .— u... ‘- m. "t interaction so that a designer can use the information directly in designing and modeling a suitable prototype. The same holds true for an algorithm which is to be pro- grammed in some language and run on some class of computers. In this section it is assumed that a language and computer are available which have sufficient capability to describe and perform all necessary computations. All accessible programs, procedures, processes and data stored in working and secondary memory constitute the environment in which the algorithm--implemented as a program in the language-- will function. Given certain conditions on the environment, an al- gorithm, S, is to direct computations on data in the en- vironment until those conditions are met. To make this more precise, define a set of calculations which need be as [I] performed by ”TI ll f. R(fi) +—-fi D(fi) D(fi), R(fi): domain, range of fi which are information structures in the computer RCfi)+—-fi [D(fii]: the results of applying fi to some elements from D(fi) are placed in R(fi) and define an m-valued decision predicate m A P 3 DCPm) + [ 01,...om} = 2 F and pm will be defined in greater detail in later sec- tions. Then the algorithm might be specified by the 3-tuple E = where F, pm are as above and h is the input- output function * 4 h: 2 ‘—»F ; Z = set of all finite strings or words (free semigroup) on the alphabet Z and is given ideally by an infinite set of pairs of the form ) h : (o f. 1’ 1 1 (cm. f im) (°1°1' fim+l) (°1°m' fi2m+1) As such h is called completely specified. Define a set of functions by left translation as follows: a: for all X62 2': hx(y) é h(xy), for all ye: If the set Ehxi is closed under left translation and is i: X62 finite, then a finite state sequential machine, M, can be derived to produce the desired function, h, in the following manner: M = <8, 2, F, 6, A, s€> where F: as above, called the output alphabet 2: as above, called the input alphabet S: the state set of M 6: 8x2 —+ S: transition function for M 1: 8x2 —+ F: output function for M and make the association 8 {h ’1 X * X62 such that to each sieS there corresponds one and only one h hye X * X62 The state transition function is defined as follows: for all 062: 5(so,o) = 5. iff si+—+ho, and s «——»h I (I) 6(si,o) iff si+—»h , sj«—+h€: y,66£ u r < and hOY a u. 1,, ~ - ,. 4 4 l" I . and the output function is defined l(so,o) = fi iff (o,fi)6 h, 50 +—+ h 1(Si,o) = fj iff (o,fj)6.hY, si+—# hY The equivalent Moore machine is easily generated from this machine and it is this model which will be used in the sequel. Although the direct relationship of the output function and the I/O function, h, is lost, the Moore model associates a calculation with only a state which will be more convenient for the purposes at hand. The (Moore machine) representation of the algorithm requires an m-way decision test at each state to direct it to further action. Thus a call to some procedure in the environment to initiate this test can be associated with each state in the program. When treating a class of pro- grams, each with its own m-way decision test, it is some- times advantageous to utilize a standardized decision logic. To this end partition each m-way test into (m-l) 2-way tests and associate with each state in a program a particular binary decision. The environment can then be thought of as simply returning to each program in the class true-false (1-0) response strings. The effect is the same as encoding the input strings in specifying h for each program. The 10 price paid is obviously an increase in the number of states in the program but in the conceptual development this is not of primary concern. It is clear that the states may be split in a num- ber of different ways. One method is illustrated in the following manner. Suppose a typical state in a Moore model representation of an algorithm is of the form where: o. 62,|E| = m, k < m 1k - then its (m-l) 2-way decision equivalent is 99m) With this breakdown and the state-only functional dependence of the output function in the Moore model, each state of the a§u 11 program is characterized by a binary decision, pi, and a calculation, fi' Hence the correspondence s.<——->(f. ,p?) 1 1 1 It is this association which will be exploited in the general model in section 1.4. In summary then, given initially a decision-calculation functional specification of an algorithm, 3 = , a finite state machine--or control--can be developed where each state is associated with a calculation and a call for some decision, with the control responding to decision outcomes as inputs. It should be noted that major difficulties in the transition from I/O function to machine synthesis arise from two considerations: (1) h is usually incomplete in that some combinations (0,fi) either never occur or are ”don't cares.” (2) h is defined over an infinite set, 2*, hence to completely specify h, a grammar or a Backus Naur Form representation together with some recur- sive definitions are required to identify, by 1': common output, classes of strings in 2 . 12 Programmers bypass (2) entirely and circumvent (1) by, in effect, designing a flowchart--essentially a finite state machine--and filling don't cares by either arbitrary assign- ment, in which case it is assumed these combinations never occur, or by effecting a terminal procedure indicating an unprocessable abnormality. This particular way of developing a finite state ma- chine from an I/O function is in the spirit of that suggested in Assmus-Florentin [1968]. Other authors, notably Harrison- Grey [1966], have algorithms synthesizing machines from se- quential functions. The concept is similar but the nature of the input-output function varies. Here only the last out- put is exhibited by the function h, when the machine processes 5: an input string from 2 . 1.4 Program Model Considerable attention has been given recently to devel- Oping models for asynchronous computation and parallel pro- cessing--see for example, Luconi [1967] and Karp-Miller [1966]. Most approaches have separately identified a control and an interpretation which together describe a specific computational procedure or program. The first attempts to apply this con- cept in programming appears to have been made by Ianov [1957] and Ianov [1958] and amplified in Rutledge [1964]. Ianov dis- 13 tinguished program control from interpretation and examined a particularly strong notion of equivalence of schemata--i.e. under all interpretations. Karp and Miller [1966] and [1967] have studied computational graphs-~directed graphs with nodes representing computations and branches as transfer of con- trol. Karp and Miller have recast their original studies on graphs along different lines reminiscent of Ianov's work. In the models of Luconi and Karp-Miller, queues are associ- ated with branches leading into and out of nodes (operators) in the control and these stacks (called links by Luconi and the u-function by Karp and Miller) are used variously to store operator initializations, operands, results of opera- tions, and certain operator or operand attributes. Because these authors have assumed a set of operations can be initi- ated arbitrarily and simultaneously, these stacks are used as working areas in each performance of an operation. Local conditions are then established on information in these stacks to investigate questions of performance (determinacy, equival- ence, etc.) within and among programs. Although the authors deal with considerations not direct- ly applicable here, it is significant that the separation of the control and interpretation functions is suitable for studying computation within a multiprocessing environment. The viewpoint here is that isolating the control flow in a 14 computational procedure so that the specific Operations to be performed are mapped onto the control to effect the procedure is analogous to, say, an electromechanical de- vice with a fixed interconnection tOpology but whose net- work parameters or a portion of the component specification are arbitrary and are required for the characterization of the device. Definitions of components of the model used in this thesis to exploit this separation are presented below. The model has three parts of which one is a computer model to underline the contention that in any program model it should be possible to relate all operations carried out in a pro- gram to a sequence of basic functions or Operations inherent in the capability of some assumed class of machines. Definition 1.1 This capability or computer representation is described by the S-tuple C = <9, B, D, F, €> where M: the location index set of the total computer memory including core, secondary storage, Special registers, etc. He II 1,m 15 3.: set of values cell ieM may assume. So if i’eM is a 12-bit register then Bi’ = $0,1,...212-1} and is appropriate for all 12-bit registers in M. B is called the * base set of the computer . D: state set of C. where a state is some assignment D = Eglg: M-»B of locations in M to values in the base set. viz. g(i)eBi g B for all ieM equivalently, D = B. . X 16M 1 F: set of all functions defined on D into D. F = [fl f: D-—+D} and IFI = DD * This notation and definition is due to W.D. Maurer. See Maurer [1966] and [1968]. 16 P: set of all finite decision predicates on D. K K 1 I pi : D fiEOI’OZH’OIJ 311K<°° U p. 1 74C: Definition 1.2 A program schema, control or, simply, schema is defined as a finite state machine: a l /cn\ M o» >a ..< U) O V 2 = [01’02’°"0L] 6 : SXX-+S A : S-+Y, a finite set of outputs 068 Definition 1 . 3 An interpretation on r is a mapping I :r —+C 'Fhe mapping I is defined by the 4-tuple I = 17 where it n: S——>F xpL with L * L L . n(sO) = (f0,p0)6F xp , and f0, p0 defined for dO n: associates with each state a finite length sequence of computations, Efi%€F*, and an L-ary decision, pEePL. y: S-+PL y: represents the environmental reSponse (the predicate value) to the L-ary de- cision predicate associated with states in S. i: c: Y-+F * g: a projection of n onto F via 3’: = F projection of (Si) C [A ($1) doeD an initial state. nginition 1.4 The specific map, I[r], will be called an interpreted schema, or a program. Note that the y mapping takes every state, 5168, into an 18 L-ary decision predicate, thereby insuring r is a completely defined machine. The key feature of the interpretation is that all elements in the control are related to apprOpriate entities in the machine class C, and as such define sequences of Operations and decisions in terms of basic machine func- tions. The three components(C,r,I) serve as a basis for es- tablishing a model which features (1) reference to a machine with sufficient capability and (2) separation of program control and interpretation. How these aspects are to be utilized must be postponed until some useful machine-theoretic concepts are reviewed. 1.5 Mathematical preliminaries To adequately define realizability and equivalence be- tween programs, certain concepts, definitions and theorems 7’: from automata and sequential machine theory are required . Given two (Moore) sequential machines: ll :3 MI <§13£19919513A19q€> ;|Q1| 1 M2 = <§20Z29AZ9623A29pd> ;1Q2l n2 9': Primary references for automata and sequential machine theoretic notions are the texts by Harrison [1965], Hartmanis-Stearns [1966], and Arbib [1969]. 19 Definition 1.5 III> M1 is equivalent to M2 iff 2 II M and (1) for all qu, there exists peQ2 such that * 11(q,x) = 12(p,x), for all X62 (2) for all p’eQZ, there exists q’te such that * 11(q;x) = 12(p;x), for all X62 i.e. M1 and M2 exhibit the same input-output behavior. Definition 1.6 M1 realizes M2 iff there exists an assignment w = (6,0,6) of M2 into Ml denoted by M1 0: M2 +2 such that - Q (1) a: QZLEEQ 2 l (subsets of Q1) i.e. a maps Q2 into disjoint subsets of Q1 . into (2) p. 22——>21 (3) g: A ”—1371 20 so that the following are satisfied (a) 61[acp),o(x)] g a [62(p,x)] for all DEQZ. for all xezz Q1 (b) €[41(q)] = 42(9) for all 969(9) 3 2 It shall be advantageous to identify and use different concepts of realizability, hence call the above an A-type realization. Definition 1.7 M2 is a homomorphic image of M1 iff there exists a 3-part homomorphism 0 = (h1,h2,h3) such that , onto (1) h1° Q1--+Q2 (2)11:me (3) h ' 9212 3' A1 A2 so that (a) h1[61(q,x)] = 62[h1(q),h2(x)] for all qu1, for all x621 (b) h3[x1(q)] = lz[h1(q)] 21 Theorem 1.1 (Hartmanis and Stearns) If M1 realizes M2 and M2 is reduced (i.e. no input- output equivalent states) then M is a homomorphic image 2 of a submachine of M when and only when the map 0 is 1-1. 1 That is: given M1 realizes M2 then by definition M1 6 : M -—+2 with 0 = (a,p,6) 2 now iff p is 1-1 then there exists 0 = (h1,h2,h3) such that ¢ : Ml’-—+M2 whereby = A0 4 W Mll <§$,fi ,61,ll,q€> 0 where W = Q1 1] E961) ] qu2] 2w = U {0(x) xe2 ] 1 2 ‘P = A1 A1 a? = 61 restricted to wazw A: = A1 restricted to Qw 22 then M1 is a submachine of M1 and the functions 0 h1(q) =9 where qeaCP) h2 = p‘1 h3=g map Ml onto M2. 0 Denote both these type realizations, H-type. A third notion of realization which shall be referred to as C-type is defined as follows: Definition 1.8 M has the capability of M iff given M and M 1 2 1 2’ o o * * a there exists an a551gnment w = (a,p ,6) of M2 into M 9: M1 denoted by w : M2-—+2 1 such that — Q (1) a: 0293522 1 23 and (a) al[a(p),p*(x)] g a [62(p.x)] for all peQ2 for all X622 Q1 (b) £[Al(q)] = 42(9) for all qeatp) g 2 The H-type realization requires that for any machine, M1, to realize another machine, M2, M2 must represent a homomorphic image of a submachine of M1--that is M re— 1 stricted to a subset of its states and subsets of the input and output alphabets with the transition and output functions defined over these restricted co-domains. When M2 is a homomorphic image of M1’ M2 is a partial compu- tation of M1. In terms of machine structure, i.e. the states and transition function, these partial computations are most conveniently described by SP partitions--partitions (or equivalence relations) having the substitution property (or right congruence). Definition 1.9 An SP_partition, or right congruence relation, on the set of states of M1 is an equivalence relation on Q1 such that qquj iff 61(qi,0) R 51(qjo); for all 062 24 The blocks of the partition are the disjoint equivalence classes of the relation, R, The machine defined by 6"(Bj,o) = BK iff 6(qi,o)eBK for all qiij provides a partial description of the way information The SP lattice of M L is a hier- 1 1’ M1’ archial organization of these units of self-contained state "flows through" M transition information. Clearly then, all submachines re- presented by SP partitions on M are homomorphic images of 1 M1. D_efinition 1.10 The correSponding SP lattice is defined as a partial ordering on the SP partitions M1 LMl = "i 9 +90909191 where 0 and + are binary operations satisfying the idem- 25 potency, commutativity, associativity and absorption laws, and for which a greatest lower bound (glb) and a least 71' Ml M1 1 ’j ' upper bound (lub) can be defined for every pair (n The elements, 0 and I, are the glb and the lub for the set M {nil}. The reader is referred to Hartmanis and Stearns [1966] for the meaning of niOnj and ni+nj. At this point it should be emphasized that state transition performance realization, i.e. realizability as in Definition 1.6 above but without the output mapping, A, guarantees realization in the full (i.e. with output) sense for every machine in some class, [Mi}’ by some state machine M1 when M1 takes on the output function of the M1 it is to realize and each Mi is a Moore machine. It has been noted by many researchers that the semi- group of a machine can serve in exactly this capacity. The semigroup is defined below and a few salient properties will be exposed. Given a state machine i=1 n ’ l 26 3': consider the input strings+ of 2 as mappings of Q1 into Q1: (211-93901 iff x(Q1) = [6(qi.x)} i = 1 n For an FSM there are only a finite number of such mappings—~ 2‘: described by a finite partition of Z , a . _ . x z =xgzaéfx] = X.yefx = fy lff x(Ql) - Y(Ql) . x.yeX Definition 1.11 The semigropp of M1, Sfil, is this set of mappings which is closed under composition 8M1 = {fX} ’0 9: X62 where fXOfYIQl] = fy[fX(Ql)] = fZ(Q1) ; z = xy ; 2.x.ye2 3% Closure is certainly apparent and adding the identity ele- ment defines the related monoid where ‘T‘ * THere and in what follows, 2 will include the null word and is usually referred to as the free monoid on 2. 27 with f oA = Aof = f x x x An alternative mathematical characterization of Sfi is a ‘ 1 i: congruence relation on 2 R8 = Efx} : xRSy iff x(Q1) = y(Ql); x,y6fX = fy RS is both right and left invariant because if XRSy, uRSV then fxof = fyOfu = fyofV . and xu(Q1) = yv(Q1) and quSyv A state machine representing this semigroup is defined with the elements of the semigroup serving as both the input and state sets. Let 8&1: <{}fx}’ {fXJ, 6 where and denote by SM the machine obtained from Sfi by restrict- 1 1 ing the input set to the generators of the semigroup, i.e. 21. This machine is described by the system 28 SM1 = ifxi * , {£0} '6 X62 062 Both the semigroup machine (or accumulator) and the related semigroup will be so designated and either will be explicitly referred to in case of confusion. ’ A 2 z 0 9 SM has all the power of SM Since SS SM as is eaSily 1 1 M1 1 shown. It will prove beneficial to relate SM to a direct pro- 1 duct of machines in the following fashion. Definition 1.12 The direct product of two machines M and M2 is defined 1 for as MlxMz = <21 Q2: 2, Ale2! 5X: AX’ (QO’ P0)> 5x[[qi’pj]'°] = [61(ql’0)’62(pj’0)] AX[[qi.ij.o] = [41(41).42(pj)] 29 Definition 1.13 The connected machine, (MlxM2)C, has as its state 58‘ (Q1XQ21r 5; le92 all pairs of states which can be reached by input strings on 2 from the initial state (q0,p0). Now given the machine M = . lQl = n define all possible machines by considering each state qieQ 8.5 a start state i=l,n then the following properties follow: (1) SM 2 [131Mijc = <[3er’z'5811> M. i qiEQ} (ii) S §[§S lcl’s SM j=l Mj M where SM = [fXJ ,Z,(SSM,fJ , fJEtf ;, [fo = m 3O ll;J S C n n M. o [1:1 1] [ilell that is the connected submachine of (iii) S n . . . [iglMi],With (q1,...qn) as its starting n state,computes as much as [iflMi]. 3’: One purpose of presenting these relationships was to show that in one sense the concept of a semigroup of a FSM is identical with that of a direct product of certain algebras defined on the machine. The usefulness of this tie-in is apparent in noting that direct product algebras usually guarantee the existence of homomorphisms from the direct product onto each factor or subset of factors. The set of all such homomorphisms with an appropriate definition of some partial ordering, is isomorphic to the SP lattice of SM. The mathematical correspondence of S and [ B M.) M i=1 1 also provides insight into the synthesis (and decomposition) of realization machines. Given any set of state machines with no initial states specified, the direct product machine These properties are actually paraphrasing the well known fact that, mathematically, the connected portion of any FSM is all that need be considered. 31 includes all connected submachines which could be defined by different sets of initial states. The semigroup of the direct product can realize any of these connected submachines alone but generally not two or more disconnected portions simultaneously. The SP lattice of the semigroup machine is the ordering of those machines and can be used to detect cer- tain decompositions of any of them. The response function and equiresponse relation and the notion of a cyclic machine conclude this section. Definition 1.14 1: The reSponse function of a machine M to any tape in 2 is the mapping 3': rpMIX) = 5MCQO,X) x62 ; rpMCX15QM Definition 1.15 The equiresponse relation of a machine M is a relation * EM, on 2 defined by EM is a finite,right congruence relation and the equivalence * classes are denoted by EM(x), xe2 . Definition 1.16 Machine M is cyclic if there exists some starting 32 state, qO, such that * QM = iqk I 514310”) = qk’ some X82 CHAPTER II CONTROL EQUIVALENCE AND STRUCTURAL REALIZABILITY In this chapter the concepts of structural realizabil- ity, program value, evaluation sequences and program equivalence will be introduced and interrelated. 2.1 Program Value and Valuation Sequences Definition 2.1 Given a program, 9, on a computer representation, C I [T] I = 1 -->6 = '11 T H then the value of T given dO is 3‘: vd0(a) = §f1,f2,...fn;, £169 where for each fi there is a state qieQ such that them] = £1. The value is defined only when n is finite. 33 34 Definition 2.2 For each d06D in an interpreted schemata,fl, with * deterministic FSM control, the string in 2 , called the valuation sequence Sd0(fl) on 2 is the tape Sd0(fl) = {01’02"'0n}’ 0162 such that if 3': vd0(4) = [f1,f2,...fn} , fieF then C [4[5(50,01)1] .—h H I H) N II C [l[5(50,0102)1] : C [l[6(50,01...on)]] H1 ll Definition 2.3 Let T = I[r] be a program with a deterministic FSM control \, q0> I : T-+ C T I Define the initial configuration - free prOgram, fl, 35 where fl II H 1‘“! H L—J OXDYté’AO q(> ,Y,€>, no initial configuration specified H II el ll /€>\ /KE>\. Notation: Let §D(Tj = E8d(1)} d6D be the set of all valuation sequences on 2 for all initial configurations for T. Let VD(T) = {Vd(§)] d6D be set of all program values for all initial configur- ations for T. Now the valuation sequence can be looked upon as an encoding--in terms of strings on a finite alphabet--of the environmental responses governing the action of the program. Some rather obvious relationships between the valuation sequences and program values are described by the following theorems. 36 Theorem 2.1 Let T be as in Definition 2.3, then for all d6D, there exists at least one Sd(fl) such that Vd(T) is always the interpreted behavior of I under the input tape Sd(T). Moreover each Sd(T) is associated with a unique Vd(T). Proof: Clear from the assumption of I being a deterministic D< The same is not necessarily true of G because of the way in which the single valuedness of G was imposed. 80 G 0 W [913(1)] 171,6?) but w o c; [SDm] SDc'qT). |n Thus while each valuation sequence defines a unique program value there may be a number of such sequences asso- ciated with each distinct value. This becomes an important consideration in the degree to which an interpreted control can model practical programs. More will be said about this later on. There are two situ- ations in which a unique relation can be made between ele- nwnts of SD(T) and those of VD(T). lgemma 2.3 Given 1 as in Definition 2.3, if (1) the maps A: Q-—+Y it c: Y——+F (2) (3) Proof: (1) 38 5': are injective (1-1, into)--so also the F projection of n is injective-~and there is no state qieQ such that 6T(qi,ol) = 51(qi'02) for all 01,0262 then W is bijective (1-1, onto). Note that W is already onto by Theorem 2.1. To show W is also injective, for any Vd(.qT) = [fl,f2,...fn} l Since A and c are injective then for each fi in Vd(T) a unique state exists qieQ, such that 6[A(qi)] = fi' Suppose there were two sequences Sd(T) = {01,02,...on% Sé(Tj = Eoi,o§,...ofi% such that W[Sd(fi)] = W[Sé(T)] = Vd(T) = {f1,...fn% 39 where §[A[rpq0(ol,oz,..oi)]] = C[A[rpq0(0i,oi,..oi)] = fi for i = 1,n. Since c and A are injective, then rpq0(oroz,..oi) = rpq0(ofioi,..oi);i = 1,n. Now because this is true for all i = l,n, and since I is deterministic, rP q O(01) = rpq0(ei) since by condition (2) above 5r(q0'°1) I 51(q0'°1)' 01 I Oi ° Similarly, 6T(q0’0102) = 61(rpq0(°lL02] 61(qi’02) = OTqu,O§) hence 02 02 . By induction then, 01 = oi , i = l,n . Hence W is 1-1. C><3 40 The following example illustrates a nonbijective W when condition (1) is violated. Example 2.1 Suppose 6T, AT and c and 2T were given by Clearly two sequences exist, {011}, {001} such that for some 0 with this I and c in its interpretation if VdO(m = [fz'fl'f3} then both sd (T) = {011} 0 sa (1) = {001} 0 are valuation sequences. 41 However, condition (1) alone is not necessary as can be seen by the next example. Example 2.2 Note AT is not injective but it can be verified that no two distinct input tapes of the same length generate the same sequence,ffi} . But it should be clear that con- i:1 dition (2) is always necessary. These sufficient conditions are easy to check. The proof of this lemma and the last ex- ample indicate the somewhat more cumbersome but necessary and sufficent conditions. Theorem 2.3 Given 0 as in Definition 2.3 iff (1) for the maps 42 there is no state qieQT such that C[AT[5T(qi,ol)]] = c[AT[GT(qi,OZ)]] for all 01,0262T and Olfoz then W is bijective. Proof: (1) Following the previous lemma: given (1) and Sd(1) [01...0n} 01,01’62T £01.. Con} w[Sd(m] = 1145307)] = [fl,f2...fn} = vd(m Sam.) then 420qu] = €014,351] = a, hence C(AT[6T(qO,01)]] = c[AT[6T(qO,01)]] and 01 = 0’ because of (1) above. 1 (Z) (3) (4) 43 By induction then Oi = Ci for all 1, hence W is bijective. If W is bijective, then there exists no two evaluation sequences Sd(T) and 83(T) for‘Vd(T) as above so that g[AT[rpq0(ol...oi)]] = g(AT[rpq0(oi...oi)] = fi for all i = l,n where (01...oi) # (Oi...o£). Then in particular C[AT[rpq0(01)]] # a[l,[rpq0(oi)] for all 01,0iEZT,Ol f oi and if rpq0(01) = ql’ then c[AT[6T(q0,ol)]] # c [ATIGTq1.0i)]]- By induction on (3). 6[AT[rpq0(ol...oi_1,oi)]] = c[AT[6T(q0,01...oi_1,oi)] 44 And since in general there is some path to every state in QT required by some d6D, this condition must hold for every state EQT. (Note that condition (2) of Lemma 2.3 is al- ways necessary for condition (1) of Theorem 2.3.) C><fl The reasons for presenting these Theorems are twofold. First, it is sometimes important to know if there is one and only one encoding (within an isomorphism) of the envi- ronmental response which characterizes any action of a program. For example, if a file structure and the control of any program manipulating that structure can be modeled by a common FSM and the conditions of Theorem 2.3 hold for both an interpretation of the FSM as the file structure, then every manipulation of the file possible by the pro- gram can be described in both effect and process by one input tape to the control. Secondly, if a programmer can fit his programs and information structures to this model, 45 he can bring a considerable amount of theory to bear in detecting common attributes even with only rudimentary knowledge of FSM theory. It is worthwhile noting that when SD(T) and VD(T) are isomorphic and one program value is identified uniquely by one valuation sequence, all elements of the interpretation and control of T must remain constant ex- cept the initial configuration doeD. Given two programs T1,‘T2 with identical controls and input alphabets but different interpretations, it is certainly possible for one tape on 2* to be the valuation sequence for two different values Vd(Tl), Vd(T2) even though the conditions of Theorem 2.3 are satisfied for each program. The point is that different interpretations on a common control relate environmental responses, to different decision predicates, with dissimilar computation sequences. Also, it should be realized that the condition in Theorem 2.3 is a harsh one to impose. This is because it says that no program can be structured in the form That is, there cannot be an unconditional transfer for some subset of input symbols from one set of statements 46 identified by qi to another set qj. Therefore, since different interpretations on a common control and unconditional control transfers destroy the isomorphic relation between environmental response and program value, it is desirable to approach the notion of program equivalence from the point of view of its values and not the valuation sequences. Moreover, when equival- ence preserving control transformations are introduced they have the property that even though SD(T) ; VD(T), there is a specified mapping from SD(T) into SD(T’) where T and T” are value equivalent. 2.2 Pregram and Control Equivalence A number of investigators have studied the question of equivalence between schemata. Generally, two schemata are equivalent if they have the same value under all in- terpretations. Patterson [1967] defined value as success, failure or divergence and, using a very general model for schemata, showed this problem is undecidable. Rutledge [1964] demonstrated that Ianov's model of schemata was equivalent to a finite machine and that Ianov's equivalence between two schemata--defined as identical value over all valuation sequences--was therefore decidable. The difference between these two points of view is how much specificity about the program behavior is con- 47 sidered in the definition of equivalence. Patterson's schemata require an interpretation to specify decision predicates and assignment statements but allow different portions of memory to be operated upon by the assignment operators. In this case different paths through two in- terpreted schemata do not necessarily mean the schemata perform different functions. In general, the problem of deciding whether two such schemata are equivalent is un- solvable. In contrast, the Ianov model assumed a specific input- output function for a schema and examined only "admissable interpretations"--that is, those assignments of decision predicates and computations which conformed to the I/O function of the schema. This restriction simplified the question of equivalence between two such schemata to one of behavioral equivalence in automata theory. 80 decidability problems being what they are, can effective use be made of an interpreted control model of a program under the restricted notions of FSM equivalence and the total memory requirement for any assignment transaction? A sizable portion of the rest of this thesis is devoted to substantiating an affirmative reply to this question. 48 Definition 2.4 Two programs 01, 02 are V - equivalent, Tl <1” iff for all initial configurations d6D, Vd(Ti) Vd(Té). Hence VD(T1) = VD(12). Notice the controls T1, 12 and the interpretations I1, I2 remain intact except for the initial configurations. As a consequence, program equivalence can be easily investi- gated from the point of view of FSM behavior. The path taken here is to not look at the behavior of the interpreted control but to examine the control structure itself and specify whee the interpretations must be for structurally related controls to preserve program value. This point of view allows one to keep the concept of control separate from that of interpretation. As stated this is an equival- ence relation among all programs possible for a given com- puter representation, Two binary relations on controls can now be defined in terms of program value equivalence. Definition 2.5 Given two FSM deterministic controls T1, 12 and a com- 49 puter representation, C, r is I-equivalent to r 1 2’ Tlirz, iff {I (1) for all interpretations on r .}, there exist 1’ li interpretations, {I’Zi}, such that I11 [T1] I’21 [I 2] <1” and (2) for all interpretations on 12, {121}, there exist interpretations, {I’ }, such that 11 I21 [T2] 5 I11 [11] ' Trivially then, Theorem 2.4 The relation, E, is an equivalence relation. H I> IQTI =n IETI =L r = ISrl = m |2F| = K i L and given a fixed computer representation C = \M, B, D, F, P then assume the set of all interpretations on r is denoted by 0 = l> l j— 52 where * n.2Q ->F XPL J T L —+P Y3 QT * Cj‘ YT —»F (10.61). 3 Theorem 2.6 Given T,C and I, if F is an A- type realization of T, then TR F, I This particular relation will be denoted TAIF. Proof: (1) If F is an A- type realization of r then via Definition 1.6 there exists an assignment w = (9,0,5) such that 53 and 6r[a(q),p(x)]e’a[61(q,x)] for all quT, for all x62T S EEAF(SI] = AT(q) for all Sea(q) e_2 F, quT. (2) The submachine of P which will be considered is rlw = <§w, 2%, Y%, A?, s;> where 8w = U a | (q) quT 2w = U [9(x)lxez i F r ‘1’ = YT YT w = - w w 6? 6r restricted to S x2, A? = A, restricted to Sw SOEQCQO). (13) Then for any interpretation Ij = { '\ J (a) Cb) 54 A new interpretation can be formed Where A w * A . : Y _..>F ; . = O . CJ I‘ CJ 5 C3 This composition map is defined by a? (y) = EochY) = chaml = chY’I = M" W where for any err, there exists a quT, and a y’eYT such that 4,qu = y». YT. ghee] = cj[y’] = f and a $6a(q) e 28 where Ar(s) = y and €[Ar(s)] = €[Y] = Y“ Then EochY) = cj[€(yl] = cj[a[l,(s)]] - c,[y’] = f. Y? 5w -+PK . Y? = ono 55 where for any seSw, there exists quT such that sea(q) e 28 and (q)=pL'D—>oo 0 =2 Yj O - 1, ZOOOL T for pL some L-ary decision predicate on D. But 9 2T -—+2F = [oi,oé...oi%, K i L hence 0(01) EXP for all oie2T. Consequently for all $6a(q) YjODCS) = o[}jCQ)] = 9[PF] = PK° The statement p[p§] = pK is interpreted to mean that K-ary decision predicate pK which makes the same test as pL but encodes the reSponses as a subset of its own alphabet based on the map 0. Hence if pL ' D -—» o o o ' 1’ 2"' L 56 then L = K - D —-> ) 1 ) z D P p . 0(01 ,p(02 ,...o(OL _c_ 1,. Finally * (c) n? : S‘” —-+F x PK where A K ”j (S) = (ftp) iff A K Yj (S) =p and a? [Ar(si] = f. (4) This completes the construction of I? . It can be seen that ] for all d6D, j 1 1 and hence IA [1] I.[T] J J =$TAIF J'.>.1 4 Unfortunately, the notation clouds a deceptively simple process. All the information the programmer needs is there 58 but it is worthwhile to emphasize what and where it is by the following example. Example 2.3 S /’ bl\-'/ b3 2 1 2r a1 32 33 AT bl b2 b3 )‘1‘ r T q0 q1 q0 q1 Z1 S0 S1 s2 51 Y1 ql q0 q1 q0 22 S1 s1 S2 51 Y2 . S2 s1 s0 52 Y3 Figure 2.1 Two State Control, I Figure 2.2 An A-type Realization of T 2, = [1,.) 1 y 59 Now r is an A-type realization for 1 since (1) O‘CQO) = $50951] S ‘ J a: QT ——+2 r “((11) = [52] (2) C(31) = 9(33) = b2 4 p ET —+Zr 9(32) = b3 (3) €(Y1) = €(Y2) - Zl A g: Y ——+Y _ F ECYB) " 22 T J And it can be verified that 6r[a(Q)a C(31)] E a [61(Q9ai)] for all quT and 3.52 l T and also €[APCS)] = AT(q) for all Sea(q). 60 Now suppose an interpretation, 1, on r was given by _ 3 (1) nCQo) ' (foapo) _ 3 (2) m0) = p3 ml) = pi (3) C(21) = f0 ;(22) = fl. Theorem 2.6 specifies the corresponding inter- pretation on r, IA, to be m 0 n .“x < l'-’ V I n F—“l m m ,.< 5...; V L____J €OC(Y2) II n r—-1 r—1 r—fi m h ..< N V w 61 I n l'_—'1 m h *< (N v L—J EOCCYS) ' | \5"( F"_l N N t——-J II H) |'-‘ (2) YA = 709 YACSO) = yopcsO) = YOp(sl) o[r(q0)] = p[p3] = p3. where if pSCD) = a1. o[pé(D)] = pg’cn) = b2 or 133(1)) = 83’ O[pg(D)] = pg’CD) = b2 or 133(1)) = 329 O[P8(D)] = p3’(D) = b3. Similarly for pi. (3) Then nAtsO) = (f0.p3') nAISl) = (f0.p§’) 0A(52) = (f1.pi'). 62 The program flow charts are shown in the figures that follow. StartE | f 0 b3 Optionall b 3. _1__-_ 9 Start [<— 0 as I a [.___>JI ., b, I "__‘> b2 > '*“" l 1"”. *’ ““*’ l I I f1 ' ' f0 9 I I a2 | I a I I . ‘41 p _ L-- 93 ._ —— l I b1 0 b l 3 a. I ' 1 1 —————————— —I Flow Chart for l[r] Flow Chart for IA[r_] Fig. 2.3 Fig. 2.4 The solid lines in Fig. 2.4 and Fig. 2.2 indicate the only cOntrol flow paths allowable in the control I. 't<3 structurally realize the control I. The inter- pretation IA on I‘ specifies the decision predicates so as to insure that only those paths are traversed. Note that P cannot be A related to r since the I 63 structure of T is not rich enough to realize the machine P for all interpretations on F. Moreover I is not actually a homomorphic image of any sub- machine in F since for this to be true the restricted input set of the submachine determined by pCXT)CZF must be mapped back onto 2T in a 1-1 manner. But in the example above b2, b3 cannot be mapped onto 2 = a1,a2,a3 in this fashion. When p is 1-1, how- ever, such a homomorphism exists and it simplifies the interpretations construction as shown in the next theorem. Idieorem 2.7 tilen Given r, C and P, if F is an H-type realization of r, TRIP and will be denoted THIF. Proof: (1) Statements (1) and (2) in the proof of Theorem 2.7 are also valid here. The additional assumptions to be considered are that the map 9: 2 -——+2 T I is injective and that the control 1 is a 64 reduced machine. Using these assump- tions an interpretation I? can be constructed from any Ij on r as follows. (2) From Theorem 1.1 and Definition 1.7, a 3 part homomorphism exists ¢ = (hl,h2,h3) where hi: SW onto QT hZ 2113-93-t—O-+2T h3: Yw onto YT and in terms of the existing map w = (a,o,€) hl(s) = q for all sea(q) e Sw p-1[2i] = 2T (0 injective) :3" N rr—fi M ”1'6 \——J ll ham} = 5W- (3) Then the interpretation I? = <3?,y?,c?,dd> is constructed as follows: H. w_,* (a) Cj' Yr F Then proceeding as in Theorem 2.6 but with (b) 65 h3 replacing E, H = ‘3‘ 1130;]. W where for any err, there exists a qgQT’ a 568w, and a'y’eYT such that - ,Y - [If * AT(Q) _ y E T, Cj[ T(Q)] "' Cj Y " 6F and h1(s) = q; seSw Arcs) = y; h,[l,(s)] = h3(y) - y’ Then CH(Y) = h 0: (y) = c h (V) - c h [A (5)] j 3 j j 3 j 3 r = . ’ = f CJIY ) H K yj: Sw——*p But here -1 y? = hloyjohZ where for all Sesw (C) 66 -l 111onth (s) II D" N I |’-‘ r_______.‘ .< U r-—fi :3" |._..I A U1 V \—___J l—————l II D" N [.1 r—l .< U O f-\ .0 U l__.__l and :3" N I H f'—_—_1 "U r' L__.___J ll '0 r—‘fi ’U L_.___.J ll *6 7S is (as before) that K-ary test equivalent to pL. It encodes the response according to p but necessarily requires the same number of responses as pL. If pL were given by '0 l"_"I '6 t" l—__l II 23‘ NI H f_'—'I "U L“ L_..—J - - -1. . = pK : D-—+Eh21(ol),h21(oz)...h2 (015\ * fig: Sw-—+F x pK where a? (s) = (f.pK) 67 iff H K Yj (S) = p c?[Ar(s)] = f. C> then In this chapter the output function of r, Ar, and the out- A T put set, Yr, are distinct for each state in r. They merely serve as unspecified variables in 1-1 correspondence with sieSr to make the composition maps in the previous chapter well defined. The theorems in this chapter involve T and there is no loss in generality. 3.1 SP Partition Realizations An easy case for which a common control can be deter- mined is when the ?i correspond to SP partitions on F. If A the SP lattice of r is denoted as where ' :1 t.) 0—1) ll ,4; w Wu. w 0') '1) M *1) / 74 and S ‘ f Bi 3,2 for all k 5?(Bi,o) = B] iff for all 553%, 6?(s,o)6Bi, for all 062?. Then the following is true. Theorem 3.1 Assume I2? I = |2f|, i = 1,m. If for any‘?i, there A . ., then P is a common con- II? is some nIeLA such that ?. Igr J F l J trol for the class, {f1}, and fiHI? for all i = 1,m. Proof: (1) The isomorphic relation ?1 g 1?; is interpreted to mean ?i is isomorphic to some submachine of F. This submachine is a homomorphic image of I and the state mapping of this (three part) homo- morphism defines the SP partition, vi. J (2) The state homomorphism identifying the blocks, {Bi}, of the partition, n§,is denoted (as before) by the hl(') 75 mapping, under which the transition function, 5T(-), is preserved. But 0 5.: F J' 2 hence 1. j hl' S-—+{Bk}. (3) Also a 1-1 onto map exists because of the machine isomorphism (4) The output map 1 . 3' Y1‘ Yri is defined in the following manner: for all erP such that Ar(s) = y, and i _ hl(s) — quT., 1 AT ,(q) = y’ 1 then i , 113m - y (5) This three part homomorphism o1 = (hi, hé, hé] determines Ti as a homomorphic image of the com- plete machine P (not a submachine) and from Theorem 2.7, riHIP. Since the map can be con- 76 structed for any Ti under the conditions of this theorem, F is an H-type common control for the class {Ti}. C> :1 Immediately then II H v 5 \Theorem 3.2 If T is the semi-control representing the semigrOUp accumulator of r, then T is a common control for Ti and Proof: (1) (2) (3) 81 riHIP for all i = 1,m. A From Definition 1.11, the states in F corres- pond to all maps on Q defined by input tapes . 3': in 2 . T +———_+ * h th t . x suc a s1 62T 6T(QT,X) 2QT So 6T(Si’o) = sj , 062r iff it S-+_———*X€Z :k s.+—————>yez and XOOCQT) = OIXCQTU = Y(QT). For any Ti with initial state q0 , the three i part homomorphism o1 = (hi,h:,h§} can be con- structed as (a) hi: Sr -—+QT i h1(50) q0i ’ 'k h1(sk) = 61(q0k,z) where sk+———-+z62T 82 the identity map, since the semigroup accumulator is restricted to the input set that is, hgcy) = y' ; Ar(s) = yaY, and hits) = q' and A (q’) = y’. Ti (4) With the existence of a three part homomorphism demonstrated for any Ti and the submachine of F identified as the whole machine, the construc- tion of IH on F for any I on some Ti can proceed as in Theorem 2.7. Hence riHIF ; i = 1,m and since this holds for any Ti, F is an H-type common control for the class Ti . The utility of this realization is that it does not recluire a priori knowledge of its existence nor does it 1163cZessitate extensive search procedures to detect it. One Sinfl‘ply generates the semigroup of the control To Then for 83 any start-state qi, use the method above to get o1 and H an interpretation I on F for some I on Ti. The decision predicates in IH are exactly the same as in I and no en- coding of responses is required because each h; is an identity map. No synchronization is required to get F started correctly for any Ti since h1(50) = q0. for all i=l,nn The price extracted for this is a treméndous in- crwaase in the number of states in F. The maximum size sentigroup for any n-state machine is nn. Even when, for reaassons of program design, analysis and organization, it is ciesirable to use this type of realization it is ill- ativiused to use up to nn states to simulate n, n-state ma- thintas. Chapter four will mention some aspects in the FWWDEKLem.of reducing the semigroup size of I using a set 0f 'tisansformations on r. .§;;§___Example of Semigroep Control Realization This section presents a complete example of developing a ‘Ssit of programs from an initial specification to the de- ssiégrl of a common control for these programs and an apprOpri- Eitfa interpretation on this control to simulate each. The meethodand type of realization is shown in Section 3.2. This example will illustrate how a semigroup realization CO . mtlrol can be constructed for a set of programs performing a tYpical housekeeping activity utilized by some file manage- 84 ment system. The activity shall be performed by a subpro- gram whose operational description is the following: Read and copy logical records comprising a set of files on a specified logical unit (disc, drum, tape, etc.) into a core buffer of Specified length. Output the buffer to a Second Specified logical unit when (1) buffer is filled or (2) an end of file is received. Whenever an end file is indi- cated on input, after the buffer is output an end file is written on the second unit. Two end files read in succession indicate termination. 7nle :subprogram will essentially direct the relevant opera- tiJDns; which are considered part of its environment. A SChematic of its relation to this environment is shown \\\\\\ \ \ Environment (C) \_ \1 input output \ T Program below. I.C. (d06D) Es , . SeTitially, the environment con51sts of hardware and soft- wa . . r13 functions belonging to the total computer representa- 85 tion, C. Thus the program output is a call to a subset of these functions—-usua11y implemented as subprograms in the machine object code or microprograms--which activates these functions and to which the environment responds by sending an input to T describing some portion of the effect of these calls. The initial configurations d eD may or may 0 not be set by the calling program of T' but are essential hi ascertaining the program value, Vd(T). One flow chart for T might be as follows: .L T‘ P——’ ——-n copy LR into .0 H buffer; read LR no I l l It'd IO ’11 l I L”______ F I ----- n---j output buffer; I end file unit; I read LR | l l I ‘T 86 I[fi] ; I = where n associates with q.1 the pair 2 . ani) = (fi.pi); 1 = 1.4 and A state copy LR into buffer; read LR get available space of buffer output buffer; end file unit; read LR end file unit end file check available space = zero : null decision - exit diagram of the control flow is given by Figure 3.4. Figure 3.4 Flow Chart of T 87 The final state, q4, is an exit and the inputs are superfluous but included for completeness. Conceivably a calling program for T might enter T'at ql, qz, q3 or q4 depending upon various editing operations performed by the calling program. Multiple entry points conveni- ently meet this requirement. But to view a program as a "black box" with input-output lines over which control codes pass, it will be useful to consider the control entry as an initial condition. Moreover, it will be re- quired that the initial conditions map onto an unspecified control flow diagram a sequence from the set [fi,p§] , i = 1,4. Thus T will be characterized by (1) its control flow diagram and (2) the initial conditions which link particular computations and decision functions with the states of the control. The interpreted control model of T is T = 1(1) (initial configuration-free program) where 88 6 are given by the table and I "<1ngng(> ‘Q—*F*> * See the discussion between Corn and Brzozowski in the article "Synthesis of Sequential Machines," in Systems and Computer Science, (p. 16), Hart, J.F., Takasu, . ed?) University of TOronto Press, 1967. where where Ar and 6 are 90 i=l,10 given by 91 S1 0 s2 0 0 1 0 s5 56 S 1 1 4 I 0 0 ° 1 I 0 s9 1 S10 1 Figure 3.6 State Diagram of Semigroup Accumulator F It can be verified that P is the semigroup machine for 4 T. Moreover, it is isomorphic to (x Ti) i=1 pondence: sl+—+(q1,q2,q3,q4) and the corresponding sz+—+(q2,q1,ql,q4) and the correSponding s3+—+(q3,q3,q4,q4) and the corresponding s4+—+(q1,q2,q2,q4) and the corresponding ss+—+(q3,q3,q3,q4) and the corresponding s6+—+(q1,q1,q4,q4) and the corresponding s7+—+(q4,q4,q4,q4) and the corresponding by the corres- input input input input input input input tape tape tape tape tape tape tape is is is is is is is 92 s8+—+(ql,ql,ql,q1) and the corresponding input tape is 010. s +—+(q2,q2,q4,q4) and the corresponding input tape is 100, 9 sla—+(q2,qz,q2,q4) and the corresponding input tape is 0100. The set of mappingSI¢II verifying the F realization of [11% . . i i i i . . . is given by ¢ = [hl,h2,h3]; h2 is the identity map and i l’ h; are defined as h j i h1(sj) s 1 ‘ h1CSj) ql qz Q3 91 93 91 q4 91 92 q2 hZIS ) 1 j q2 q1 q3 q2 q3 q1 q4 ql q4 q2 h3(s ) q q q q q q q q 1 j q3 1 4 2 q3 4 4 1 4 2 4 h1(sj) q4 94 94 94 94 94 q4 Q4 94 94 Note that since XFISj) = 2.. A (qk) = Yk therefore I ‘< 7:. H m r—h :3" I—lI—I- A In W I ,0 w i h3(Zj) Since I 93 = <3,y,;,dé> is the common interpretation for all controls Ti, and ”(qi)==(fi’pl)' i = 1,4 where f. and pi are defined appropriately, the interpretations l I? = * are defined by (l) c‘fIzj) = h§ o ciCZj) = ci[h§(zj)] and can be read directly from the hi, hi above and the map ti(yk) = fk' (2) Y‘jcsj) = h] o vi(sj) = “[11359] (also directly from hi table). (3) Combining l and 2 the table for n? is S1 s2 s3 S4 s5 56 s7 58 59 S10 "I(5j) £191 fzpé f3P3 f3p3 f3pg flpI f4pi flpI fng fzpé ”7(Sj) fzpi flpI fspi fng f3p3 flpI f4pi £191 f4pi f2P2 ”3(Sj) fspi £191 f4pi f2P2 f3P3 f4pi f4pi flpI f4pi f2P2 ”gcsj) f4pi f4pi f4pi f4pi f4pi f4pi £492 f4pi f4pi f4pi 94 At this point all that remains is to implement F as a subprogram in FORTRAN, building in the control flow according to the transition function, 6 but parameteriz- I1, ing the computations and decisions made at each state. The control flow chart together with its parameterized subroutine implementation follow. Each state Si is considered as a combination of a calculation and decision in Figure 3.7. Start 0 1 " S1 S7 exit Figure 3.7 F Control Flow Chart 10 20 30 40 50 60 70 80 90 100 500 95 SUBROUTINE GAMMA (Sl,SZ,S3,S4,SS,S6,S7,S8,S9,SlO) IF IF IF IF IF IF IF IF IF IF RETURN END (Note: (S1 (52 (S3 (S4 (S5 (S6 (S7 (S8 (S9 (510 (DUMMY)) (DUMMYD (DUMMY)) (DUMMYD (DUMMY)) (DUMMY)) (DUMMY)) (DUMMYD (DUMMYN (DUMMY)) 500, 500, 500, 500, 500, 500, 500, 500, 500, 500, 20, 30 40, 50 60, 70 20, 50 80, 70 90, 30 70, 70 100, 50 60, 30 80, 50 the argument "DUMMY" and parentheses are required in FORTRAN to distinguish external function sub- programs.) Figure 3.7 (Cont.) Parameterized Subroutine Implementation A feasible set of functions and predicates could be incor- porated into the following FORTRAN function subprograms: 10 20 10 20 96 FUNCTION 01 (DUMMY) COMMON A, B, N, MX, CALL COPY (A, B(N)) CALL READU (INU, A) IF (EOF, INU) 10, 20 Q1 = 1. RETURN 10 Q1 = 0. RETURN 20 END INU, IOU FUNCTION QZ (DUMMY) COMMON A, B, N, MX, NDIF = Mx - N IF (NDIF.LE.0) 10. 20 02 = 1. C RETURN 02 = 0. RETURN END INU, IOU Note: INU: IOU: FUNCTION Q3 (DUMMY) COMMON A, B, N, MX, INU, IOU CALL OUTBUF (IOU, B, N) CALL ENDFILE (IOU) CALL READU (INU, A) IF (EOF, INU) 10, 20 Q3 = 1. RETURN Q3 = 0. RETURN END FUNCTION Q4 (DUMMY) COMMON A, B, N, Mx, INU, IOU CALL ENDFILE (IOU) NULL DECISION - FORCES RETURN Q4 = - 1. RETURN END A: temporary storage for logical record B: output buffer N: running index of used cells in B MX: maximum length of B (= integral number of logical record lengths) number of the input logical unit number of the output logical unit In each function subprogram, Qi, the computation, fi’ and the predicate, pi, is easily discerned. The interpretation mapping n (of I) is used directly to indicate the proper computations and decisions to be included. The "states" of GAMMA are defined when variables declared as external 97 functions in the calling program are used in the GAMMA call parameter list. Exactly how to line up the function programs Q1 to Q4 in the arameter list is revealed expli- citly by the mappings n? . i=1 appear as. PROGRAM CALGAM EXTERNAL 01, 02, 03, Q4 C CALL MACHINE TAUONE CALL GAMMA (01, 02, Q3, C CALL MACHINE TAUTWO CALL GAMMA (02, 01, Q3, C CALL MACHINE TAUTHREE CALL GAMMA (Q3, 01, Q4, C CALL MACHINE TAUFOUR CALL GAMMA (Q4, Q4, 04, \ The calling prOgram would 4 9 Q1. Q3. Q1. Q4. Q1. 2. Q2) Q2. Q3, Q1. Q4. Q1. Q4. Q2) 29 Q3: Q4: Q4: Q1: Q4: Q2) Q4. Q4. Q4. Q4, Q4. Q4. Q4) 98 The subprogram F appears dependent upon three branch logic whereas the environment can only give the program strings of two symbol inputs. However, the output to the environment from any final state indicates termin- ation which, as a practical matter in FORTRAN, cannot be accomplished except by proper program exit. The third branch to the return statement can be considered as an activity of the environment providing no ”input" per se to the machine nor requiring any further machine response. Since programs always require some set of terminal points or states, as a practical matter their implementa- tion as statements in any programming language necessitates including fixed exit points in the procedure. One cannot, as a rule, terminate a program in a higher level language after any statement except by transferring control to one of these legitimate exit points. So while each control has a set of these states where an interpretation maps these states onto a "return” function, the control must be imple- mented so it can turn itself Off by transferring to one of the legitimate exits. From the control point of view, when the final or terminal state is reached, the control is in- active until restarted at a later time. For any programming language including a set of processor interrupt commands, no artificial devices such as that above are needed to effect 99 termination. Without this feature, common controls must, in general, provide the facility for proper termination at any state. This is one implementation problem, among others, which is circumvented with the next type of reali- zation. 3.4. Composite Realizations This section introduces a model of the most natural way of combining a number of distinct programs. The funda- mental idea is apparent from the following example. Example 3.2 Let two programs Ti, 12 whose flow charts appear in Figure 3.8, have the controls of Figure 3.9. Suppose inter- pretations are imposed on these controls by subroutine calls with external functions in the parameter list: PROGRAM MAIN ExTERNAL 011, 012, 013, 014, 021, 022, 023 C LL PI (011, 012, 013, 014) ooo>oooooo CALL P2 (021, 022, 023) 100 SUBROUTINE P1 (01, 02, 03, 04) 1 GO TO (2,3) 01 (D) 2 GO TO (3,3) 02 (D) 3 GO TO (4,3) 03 (D) 4 GO TO (1,5) (34 (D) 5 RETURN END SUBROUTINE 92 (01, 02, 03) 1 GO TO (2,3) 01 (D) 2 GO TO (3,2) 02 (D) 3 GO TO (1,4) 03 (D) 4 RETURN END If one were asked to write a common control (in the above form) to implement both procedures, he might respond in the following fashion. Flow 101 (a) T, Figure 3.8 Charts of T l, T2 102 Start f5 q21 0 P: 1 L qzz ' \’ f6 q23 f7 0 Pg 1 //:>\\ 0 q24 end (b) a, Figure 3.8 (Continued) Flow Charts of T1, T2 103 Figure 3.9 Controls T1, 12 q21 q23 q24 104 SUBROUTINE P12 (Q1, Q2, Q3, Q4) 1 GO TO (2,3,2,3) Ql (D) 2 GO TO (3,3,3,2) Q2 (D) 3 GO TO (4,3,4,5) Q3 (D) 4 GO TO (1,5,2,3) Q4 (D) s RETURN END And the calls in MAIN CALL P12 (Q11, Q12, Q13, Q14) CALL p12 (Q21, Q22, Q23, Q21) simulate P1 and P2 respectively. The decision predicates associated with each external function are modified so that the value of Qi(D) is l or 2 (3,4) for program Ti (12). The common control, P, of subroutine P12 can be modeled by a composite construction using the two controls T1, 12. The control I has five states so P must have at least this 1 many. Hence, let ‘ SF = E51] 1 = 0,4 Now IQT l = 4 but there always is an n-state equivalent con- 2 trol {to r2) where n>4. One such S-state control for 12 is pictured in Figure 3.10. 105 Figure 3.10 S-State Equivalent Control for 12 Let the input alphabet for r be 2:r = }°10’011'°20'°21} (where o = 3, 021 = 4 in the FORTRAN 10 = 1, 011 = Z, 020 implementation) and the transition and output function be defined as: I": 1‘ 50 s 106 Clearly the transition behavior of states of F under {010,011} is precisely that of T1 and similarly for 12 and the inputs £020,021}. The construction simply makes a c0py of each machine on a common grid by identifying separate inputs to each machine. Each control Ti)is a homomorphic image of F via the maps ¢1 where ¢1 = [h%,h%,h%], ¢2 = [hi,h§,h§] and [$0 $1 $2 53 54 J50 S1 S2 S3 S4 1 2 hl(si) q11 q12 q13 q14 q15 h1CSi) q21 q22 q23 q21 q24 w 4 h; 2 1-—+ Z hZ: Z 2-—+ Z T T1 2 1" T1 1 2 h2(olo) — 0 h2(020) 0 11 2 12(011) 1 h2(021) 1 hr YT ——+ 1T1 h 1F ——+ YT2 idlere 1.1 = , 107 P is then a H-type realization for both T and T with 1 2’ the appropriate submachines (recall Theorem 1.1) of F described by I” where w. 1 = 51‘ SI‘ 2W1 o o ' sz " o o F 10’ 11 ’ F 20’ 21 w. . 1, 1__* 6r . SFXZ SF w. 10 AF . Sr—+ YF' The construction of the proper interpretations on F for r to be a common control for {11,12} follows that of Theorem 2.7 and one implementation of these constructions is via the calls above. Recall that for some I = on, say 11, w- , 7H: SF1-—+ P4 Since IZPI = 4, if H - 1-1 1-1 2 4 y (s) = hiofihfil 1(s) =(h2) [you] = (112) (p ) = p where if p2: D-—+E0,l} 108 then (hfil'ltpz) = p4: D -+k-§)‘1(0).(h§)'1(13} = {010.011}- And the decision predicates defined by the maps in 1H make the same tests as those specified by I but encode the responses as a subset of Z Note also that the state r. homomorphisms mapped the starting state of Sr onto those of T1 and 12 as with the terminal states. This is always possible for interpreted controls with one exit point. Before the general construction method is presented,a means by which equivalent machines are generated is re- quired. Definition 3.2 For any cyclic control I completely defined for some input alphabet 2T, define the set of minimum grids, GT, as that set of pruned (i.e. all but tree branches eliminated) reSponse trees of r for which each node represents a dis- tinct state in QT and the path length from the root of the tree to that node is the smallest possible. /‘ 1‘ > G = i , i = \ >X-4 T 1g} g \1J"=1,n-1 ° * where to every quQr’ there exists x§ezT such that i 51(q0’xj) = Qj 109 Example 3.3 1, 12, in Example 3.2, 611’ GT2 are unique and are shown in Figure 3.11 (a) and (b). For T q q11 21 0 0 1 Q12 1 q22 q23 q13 0 1 q14 q24 q15 (a) (b) C = 0,1,101 CT = 0,1,11 1 2 Figure 3.11 Minimum Grids G , G T T l 2 That is, there are no other trees on which the states ofrland 12 can be mapped so that the path lengths from qi1 are i=1,2 less than those above. Example 3.4 This example shows that CT is not necessarily unique for any 1. Consider the control, T, in Figure 3.12. 110 o 1 5T q0 q1 q2 GT qo q0 q1 q0 q3 0 1 0 1 q2 q3 q2 q1 o qz ql q2 q3 q0 q3 q3 . l q3 (a) ' (b) Figure 3.12 Multiple Minimum Grids The following theorem is trivial from the standpoint of finite state machine theory but it references a particular construction which shall be referred to in the sequel. Theorem 3.3 For every cyclic n-state control, I, there is a set of m-state controls Lm[r], for any m :,n called the labeled extension of r, where each machine in Lm[r] is behaviorally equivalent to I. Proof: There are a number of ways to construct such machines, for convenience Lm[r] will be restricted to the method pre- sented here. (1) Pick any tree from GT and label from s to s O n-l the nodes or states in some standard fashion starting with the root qO as 50 and descending the tree from left to right numbering consecu- tively each encountered state. Redefine the (2) (3) 111 transition function 61 for this relabeling. Let this relabeled machine belong to Ln[r] and define Ln[r] to be all relabeled machines generated by GT. Since T is cyclic at least n-l entries in the state table exist which define any such tree. All other entries correspond to those arcs eliminated from the grid. Identify any such grid gieGT as a subtree in the complete response tree over ZT for the re- labeled control T. There are at least n-1 (and no more than n) nodes from which arcs can lead out of gi and generate new subtrees. Label any node in the response tree not in the subtree gi and reachable by some arc from a node 5. in gi J as sn. Then the n+l-state equivalent machine to r is constructed by redefining 61 as follows: i * i (a) If for node, sj, xjeZT, xjegieGT 1 _ . . _ , , and 61(50’Xj] - sj , gin 1 1n tne relabeled n-state machine I, and .. i 1 if x.o¢g., some 0:2 J 1 r then . l — -- o —. 5T(SO,XjO) — 61(sj’0) — Sk’ kin l. 112 (b) Redefine 61 on state sj as i 6T,(so,xjo) = 6 ,(s.,o) = s r J n and define i 61,(50,x. 3002): 5 r’(sn’0£) = 6I(Sk’oi) for all o 52 2 r At’(sn) = AT’(Sk) 6 , = 6 , A , = A otherwise . T T T (c) Then T = QT” 2T, 61” AT” YT,, 50> where QT, = QT U {Sn}; Q1: the relabeled states of r and C) .4 \ II M 00 H. W . 00 H' \ II 1 gi U Exjo], gieGT. (d) Then I is behaviorally equivalent T, an n+1 state machine €Ln+l[T]o (e) Set I = T; GT = GT, and continue the process until IQT,| = m . (4) Lm[r] then contains those machines which can be constructed in this fashion, all of which are equivalent to r. I“) /) V" 113 Example 3.5 Consider the control and grids in Figure 3.12(a) and (b). A number of labeled extended S-state equivalent machines with representative grids for this machine are given in Figure 3.13. s S 51 52 $1 $2 51“: 52 s s 3 3 S4 S4 53 s 4 O l O l 0 l 61’ s0 s1 52 s0 s1 $2 s0 s1 52 r‘. s1 s0 s3 51(33153 s1 s0 53 s 5 §\ 5 s s s s s 2 3L4) 2 3 2 2 3 2 f s3 s0 $2 s3 s0 $2 53 5045—4 s4 s3 s4 s4 s1 s2 s4 s3 52 Figure 3.13 S-State Equivalent Machines in L5[r] Theorem 3.4 A cyclic deterministic n-state control, I, is the homo- morphic image of any m-state labeled extension r’eLm[r], m i no 114 Proof: (1) For.every machine r’e1n[r], each state si was a relabeling of qieQT, hence h1(si) = Cl 11 z ,-——+ Z ; hi: the identity transformation N\ F; H h’: Y ,———+ Y ; h’: the identity transformation a; (2) To generate some machine I eLn+l[r], sn was neces- sarily behaviorally equivalent to some Sj’ j = O, n-l hence hi’(si) - ql, 1 = 0, n-l hi'rsn) - hflsj) - qj h2’ = hi hg’ (yi’) = yi, i = 0, n-l hg’ of) II ‘< A ~ (Sn) = yg’. 4,013) = y (3) Continuing in this way the 3 part homomorphism can be defined for any machine in Lm[fi] onto 1. I> such that (l) [Srl = m, where there exists Tj’ j = l,n,such that Q = m > Q for all k = l,n. Tj — Tk n (2) z = 2 2 , 2 =0 U o . I Fl i=1 Ti i=l,n j=l, 2T 13 i (3) riHIP for all 1 = l,n. Proof: (1) For any control, say Tj' with the largest number of states Q T = m i Q for all k = l,n Li Tk pick any m-state labeled extension of Tj from Lm[ri] and let this set of labels si be i=0,m-1 the state set SF' 116 This set of labels is common to all L [h.], m 1 i l,n, and for each Ti, pick one m-state labeled exten51on TiELm[Ti]' (2) Define the injectiVe map hi'l i-l, l-l . hZ ' 2T1 into {Oij} J = 1, ET. . 1 (3) Then GF’AF are defined by _ i _ 6TCSk’Oij) - 6Ti[sk,h2(oij)] k - 1,m j = l, 2 lr(sk) = Yk ; k = 1,m. (4) Consider each submachine of F of the following form “’1 11). 1 SP = SF 1 _ J = 1’ 2T. 1 W 4- 1 1 (SI erzr —’ Sr w. 1 _ AI, — AP. (5) Remark: 117 These submachines are isomorphic to the chosen r’eLm[ji] and since each Ti is a homomorphic image of Ti from Theorem 3.4, replace the identity input alphabet map of that theorem with h: above, hence verifying that Ti is a homomorphic image of the submachine P under the three part homomor~ u’1 . i _ i i i . ph1sm ¢ — [h1,h2,h3]. 1p. 1, 1 hl' ST -—+ Q1. 1 1]). h; 21,1 —+ 2 Ti . w. 1, 1 h3. Yr —+ YTi The conditions of Theorem 2.7 have been met, hence F is a common control for Ti and riHIF for all 1 = l,n. t><3 Now if only one exit point is identified in every program I[ri] it is easy to see how the relabeling process can be constrained so that for every such exit state qieQT then i i e e . . e . . h1(sm_l) = qi ; 1=l,m 1f sm_1 +9 ex1t state in r. 118 This eliminates the necessity of introducing superficial transfers to the F exit states as in the Section 3.3 example. The example introducing this section illustrates this pro- cess. For every program with an n-state con- trol and a number of exit states, one additional state can be added to form an n+1 equivalent control where all exits are made via transfer to this state. Hence this particular structural realization facilitates a simple implementation of any program I[Ti] on F. The extension of the Ti to m-state equivalents is advantageous not only in this regard but also to provide a completely defined control P over the augmented input alphabet Z The example of this section 1‘. also shows the straightforward fashion in which the decision predicates are modified for any interpretation~-a direct consequence of the in- i 2 tural realization. jective map h characterizing the H-type struc- CHAPTER IV MINIMUM STRUCTURAL REALIZATIONS Having examined some H-type common control realiza- tions, Sections 4.1 and 4.2 introduce another H-type realization which also can be constructed for any set of cyclic controls. 4.1 Subdirect Product Realizations Product algebras are common mathematical constructs of systems which preserve all the capability of their com- ponent algebras. Not surprisingly, a direct product of finite state machines is a useful device to construct H- type common control realizations. The semigroup realiza- tion was of this nature and the method in general is de- scribed by Theorem 4.1. Theorem 4.1 Given a set of deterministic, cyclic, FSM controls; the control ’j II n c [ x 1.] over 2 = Z ' i = l,n . 1) 1 M r—W—x rd—\ .0 U. in .0 L4. v v .0 U. :1 \——_J \-A_._/ v "1 M "J v *-< ’_J v 07 "3 o >’ ”'1 v ,0 O v o o o o a ,0 O :3 w 120 is a H-type common control realization and T-H 1 IF ; 1 = l,n. Proof: An outline of the proof which is quite similar to that of Theorem 3.1 follows. (1) It is clear that the component controls Ti are homomorphic images of F since I i 3 qjiEQTi S = . ... . F [[qjl’ ’qJn * where there exists xezr such that 1 _ i i i then Q [hl,h2,h3] where i. (a) hl' SP-+ QT_ 1 hi . . . . . . = . for all ' = l 1 ququi Squ’ qun qu 1 an for all j = l,|QP| 121 (b) h; = identity map for all i (c) 11% up = y; iff A1.(sk) = yk and .i _,_ Ari[h1(sk)] - yi , skEST (2) The submachine of the homomorphism is F it- self and the conditions of Theorem 2.7 have been met. D>> on Ti the map Wij: SD[Iij[Ti]] ——+ VD[Iij[Ti]] is bijective then H , m -H___—' '” '7T_——' - -- - wij' SD[Iij[r]] ——+ VD[Iij[r]] is bijective. Proof: (1) If Wij is 1-1 and onto then by Theorem 2.3 ([1) MN for any qk.€Qr.; for all 0,0 EXT. = Zr, 0 £ 0 1 1 1 or i: O O .. , . . . . . 6T. AT. c13(qk ) 2T:—+F lS injective 1 1 1 1 The same must be shown for 6F’ RP and Cfij’ (2) For any Sk = [qk’qk 9°°°sqk_s°°°aqk J l 2 1 n 56 = [qfili'°’qP-"°’qmni; APismi = y’; ATiiqmi] = 2’ l 123 such that _ i = 5F(Sk90) - Sm, h1(Sm) qmi ; _ ’ i I = ’ 6I‘(Sk’O ) - Sm’ hl(sm) qmi then condition (1) says that cij h§[xr[ar(sk,0)]] # cij h§[kr[6r(sk.0’1]] f0? 0 f 0’ or W41] . 1141.141] because h§[xr[sm]] = h§(y) = z h§[lr[%{]] = h§(y’) = z’ and Cij(z) # Cij(z ) But this is true for all sk, so i . ' o - cij h3[*p[5p(5k:0)]J is unique for distinct con- trol input symbols, och, or equivalently the map ioz; (s)=<3 124 This theorem provides a mathematical way of expres- sing the notion of simultaneity. For if the conditions in Theorem 4.2 hold and one considers the set ] C i§D[IiI;[I‘] n '1 N isj 113m 1.1 then every valuation sequence in x describes one and only one value for each of the programs Iig[r] on some initial configuration deD. Hence one input tape to the control P can describe the simultaneous execution of any programs {Ii?[r]}, and consequently Elij[ri]} and their values Vd[1ij[Ti]]i for some {d}eD. This property cannot be true for composite realizations in general because the in- put alphabets of the individual controls are of different size and two different submachines in F usually cannot serve to simulate the same control. Composite realizations then cannot serve as models for parallel processing but could adequately model a set of programs time sharing a central processor in a multiprogramming environment. Direct product realizations can serve both causes but at the expense 125 of introducing many redundant states. The following rather detailed example illustrates the direct product realization for two typical numerical analysis algorithms and introduces the idea behind the control transformation which will be discussed at length in later sections. Example 4.1 Consider the following two flow charts for Runga- Kutta and modified Newton-Raphson algorithms in Figures 4.1 and 4.2. 126 variable initialization DFLAGfi—(DFLAG + 1)*§(EIH)Z I I I I I I I Com I I ' I pute R r2 I I I_ ___________ I | I | I I <1‘R 5. EP8 esh)‘ r_.':::: Jfl53___1 Com te F r4 I pU (X) Xi+1 : | I__________ es(H) II0(0) —] ;[___T_<:::’E/;f// Scale+-l/21 I 1+1 L. ____________ _Ino(OI Figure 4.2 Newton-Raphson Scheme for Solution to Nonlinear Equation F(x)=0 129 The method uses the following convergence and improve- ment tests (governing convergence rate): F(x-) x. = x. - H* ———i——- if two improvements: H+ 2*H 1+1 1 F’CX) i if one improvement: H+ H if no improvement: H+ H/Z where the improvement test is F(Xi+1) < F(xi). . Ixi.1I-Ixil , , The convergence test used is =R.—.EPS:(relative IXi+1I+IXiI error). The iteration limit = ITL, and the quantity 2(11 < HLL) V (IL: > ITL)Z is binary valued (O or 1). The controls T1 and 12 and the n11, n21 maps for IllITII’ IZIITZI appear in Figure 4.3 (a) and (b). 130 1 r5 3 6 . 0 1 T1 n11 T2. 1 t2 n21 2 2 q1 q2 q3 y1 (flpl) r1 r3 21 (fépé) 2 2 q2 q4 q1 y2 (fzpz) r2 r3 Z2 (f7p7) 2 2 q3 q1 q5 y3 (£393) r3 r3 23 (fsps) 2 2 q4 q1 q5 y4 (f4p4) r4 r1 Z4 (fgpg) 2 2 qs qs qs y5 (£595) r5 1 r3 ZS (floplO) (a) (b) Figure 4.3 Controls for Runga-Kutta and Newton-Raphson Programs 131 Now for - = r 0 = P - 11x12 , s0 (q1,r1) it can be shown that |(QT XQT )rl = 24. But suppose the 1 2 state transitions in 11 and 12 were changed as in Figure 4.4 (a) and (b). Then for these controls , , _ r I‘ = 1' 1X1 2 - <(Qr ’ler ,2) ,Z,YI,,51,,SO> ((2,.1><<2,.2)r = 11. resulting in the reduction, 5r’1: 0 1 ”’11 61’2: 0 l n’21 _ q1 q2 q3 (fipi) r1 r3 r2 (£653) q2 q4 q1 (fzpi) r2 r3 r4 (£75?) q3 q1 qs (f3pi) r3 r3 r3 (fafié) q4 q5 q1 (£454) r4 r1 r5 (£953) q5 q5 q5 (£55?) r5 r3 r1 (£10310) (a) (b) Figure 4.4 Transformed Controls 1’1, T’z 132 The associated semi-control, I, is shown in Figure 4.5, and 0 6? : s1 52 53 S2 $4 $5 $3 $5 56 S4 S7 S5 S5 S2 S8 56 59 510 S7 S7 S7 S8 S2 S7 S9 S7 511 S10 S7 S9 S11 S7 56 (qZ’TS) $2 (qS’rZ) S3 ((1.1‘15 (Q.r)s 4 3 . (q1,r3) 55 5 4 6 @6 (QS’rl) 9 q5,r5) 510 Figure 4.5 Direct Product of Transformed Controls 133 the maps hi, h2 are shown in Figure 4.6. 1 1 h1(si) q1 q2 q3 q4 ql qs q5 q3 qs q5 q5 2 hl(si) r Figure 4.6 State Homomorphisms of F onto T1 and 12 The appropriate maps ”I1’ ”21 are read directly from Figure 4.6 and Figure 4.4 (a) and (b). The implementation of F in FORTRAN follows closely that of the example in section 3.3. Notice the permutation of the entries in the transition tables for 11 and 12 in Figure 4.4. In T1, the transformed transition function, 6; , reads as 6;1 (R4. 0) = 6T1 (Q4. 1) = RS 6;1 (Q4. 1) = 6T1 (q4. 0) = q1 Now if the binary decision predicate pi is changed to 53 so that 2 _ -2 _ p4CD) - 0 :%>p4(D) 1 2 _ _ 2 _ p4CD) - 1 é>’p4(D) 0 134 then the program Illfrl] has exactly the same value for any deD and all valuation sequences for Illfrl] are ob- tained from those of Ill[TlI with certain zeros replaced by ones and vice versa. This is the essence of the trans- formation which shall be considered in the following section. 4.2 Value Equivalent Control Transformations For the rest of this chapter all controls will be defined over a binary input alphabet, {0,1}. The results and notations can be extended over an arbitrary number of symbols. Definition 4.1 For any FSM control . =; IQ,I =n. 2, = {0.1} define a reordering of r to be the control where if the n-bit binary representation of i is . _ n-1 n-2 l (i)10 - bn_1 * 2 + bn_2 * 2 +...b1 * 2 + b0 * 2 and ° _ , . < ° < 135 then if bj = 1, i ll 0') fl ,0 o I—‘ V T 5 (ero) ll 0‘) r-\ .0 V O V 6 (qj.l) 5 (sto) 6 (Qjao) 3 05 {091} '1' Example 4.2 (1) Clearly (2) For controls T1, 12, in Figure 4.3 (a) and (b), the transformed controls represented in Figure 4.4 (a) and (b) would be denoted by 8 27 . . 11 and 12 reSpectively. Since (8)10 = (lOOO)2; then I 85 O = 6 l = ,1 (Q4. I ,1 (R4. I RS 8 I since b4 = 6,1 (Q4.1) = 6,1 (Q4.0) = q1 and similarly for 2712, where (27)10 = (llOll)2. 136 Theorem 4.2 For any class of controls {Ti} such that for some r = <81” 2,, Y1" (51,, 1,, 50\/ , 'er = n, 2,, = {0,1} then P is a common control for Ti and Proof: (1) Let I be any interpretation on Ti. Define 1I as that interpretation on P which is to be constructed so that f i ‘ vd IIITiII = vd I 1[r]I ; for all deD. (2) If 1I = (in, 1y, 1;, ;\ and (1)2 = Ibn_1, bn_Z,...b1, b0] ; 2 b.€ {0,1} , J = 0, n-l then set (a) c=c i 2 (b) y : Sr—-+P 137 where if 2 2 . = . P (SJ) RJ 8 then i 2 . s. = . f b. = 0 Y( J) P3 1 J i 1—2 . s. = . f b. = 1 Y( J) PJ 1 J and if 2 _ —2 , _ pj (D) - 0 then pj (D) - 1 2 _ —Z _ pj (D) — 1 then pj (D) - O. (c) . 2 . i . 1 . = f. . ff [1 s. 1 = f. n(SJ) (3.123) 1 c 1.(J) J i 2 and s. = .. Y C J) PJ (3) Now for any state, Sj’ such that bj = l and rpS (01,.,0£) = sj ; 0ke{0,l}, l £.k i 2 0 let us.) = p? and p; (D) = o. J J J Now suppose 61(Sj»0) = sm. CorreSpondingly <5 (5 O)=i0 For an illustration of how reordering applies to SP partition realizations (recall Theorem 3.1) consider thefollow- ing case . Given a control, r,‘such that the semi-control, ?, is isomorphic to the SP partition, {13, 2, 4), of 3? in Figure 4.7, it is clear that no such partition could be un- covered from the trivial lattice, L But if all lattices 0? 142 o. __94..1 1- ___91_1 2, 0 1 3, 0 1 r 1 23 r 1 32 r 1 23 r 1 32 2 43 2 43 2 , 3M 2 34 3 12 3 I 12 3 D2 3 12 I‘d— I 11. 4 24 4 24 4 24 4 24 I II II II L - L , I 13,2 4 L , I L 2 I 13‘? 4 0F 1? II ’ I 2? I 3? II ’ ’ I 0 .0 I 00 '0 I3 /A,V‘ "72/713- / 1‘ 0 “/I 1 0 )2 -. \2 /’ O 1 0 f 1 . 4 AK? ‘ \F‘ o *\, 0 \_l 1 Figure 4.7 A f and the Reorderings, 1T, i = 0, 7. 143 0 1 _in 0 1 ___ 0 4f 1 23 5‘ i—I 23 6‘ 1 23 7“ 1 I_32 2 43 2 43 2 34 2 34 3 21 3 21 3‘ 21 3 21 4 24 4 24 4 ‘24 4 24 Figure 4.7 (Cont'd.) T and the Reorderings, 1F, i = O, 7. 144 for if were searched, that very machine would be uncovered for the reordering, 3?. Uncovering the lattices requires searching (Zn-l)/2 reordered controls because of Theorem 4.4. This procedure is tedious but well defined and the algorithm for SP partition generation only need be carried out to k-block partitions on F when trying to find an isomorphic machine to a k-state control, ?. The work can be cut down further if it is realized that when one k-block SP partition is found for some if, is? can be changed for every state in any of the blocks to generate a new reordering on i? which has the same k-block SP partition in the SP lattice but whose machine structure differs from the partition in i?. For ex- 3 ample 1? and f both contain the SP partition {T3,2,4) in their SP lattice and their transition functions differ only 1 on state 2. The same is true for P and 4T, where 16f 2 46A F on states T and 3} In all cases the associated machine structure for {T3,2,4) is different. It is not possible to detect all k-block SP partitions by examining reorderings on just one k-block partition, but all those partitions which group the state set in the same way as the original can be uncovered by a set of reorderings. To illustrate this, note that all re- orderings on if identifying the states {I3,2,4} can be deter- mined by reordering states 1 and 3,2, or 4 in any combination for the machine 1?. The point is that reorderings on un- 145 A covered SP partitions in P may produce the desired iso- morphism to the given ?. The case for semigroup realizations requires as much if not more work. One must determine that reordering on ?--for which each member of the set {ii} is the control ? for a different starting state in QT--which produces the smallest semigroup accumulator, ?, realizing each semi- control, ii. If f has n states, its semigroup could be close to the maximum size, nn. Consequently, determining the semigroup by ascertaining the closed set of state functions fX: Qf—+Qf is not practical for large machines. There are two conditions which appear to be useful here. It is well known that the right-congruent response relation on any finite machine refines the congruence re- lation associated with the semigroup of that machine. The power or computibility of the machine might be thought of as the rank of the (semigroup) congruence relation. It might be expected that as the number of SP partitions on an n state machine r increases, for some reorderings iT, then in some sense the semigroup sizes decrease. The fol- lowing theorem indicates in what sense this is true for a restricted class of controls. 146 Let T : the class of all FSM semi-controls with n states over a binary alphabet. Let Sfi : semi-group accumulator for control, MET ISfiI = number of states in SQ. Let Tk g T that class of machines which have at least one n-k+l block SP partition with one block having k elements, all other blocks having one element. Then for all MeTk, there exists a neLM such that I n = IBl,B2,...Bn_k+1I I(qi aqi ""qi J: qi ’qi ’°"qi I l 2 k k+1 k+2 n \‘_,_\Vim,m_wmiix’ n—k blocks Theorem 4.5 max ISQI i (n+2) * nn-Z = nn‘l + 2*nn-Z MST n 1 max ISfiI = n MET Proof: (1) (Z) (3) 147 Now Sfi g I¥M.I where M 1 i and the state set of SM is isomorphic to IIjngRIIr = IIqjl,qu,,,,anIIr i: 2’: where there exists a xjez = {0,1} such that and M. i ' < ' < for 1 —.j — n, Iqj1.qj2.anI = Iémqlmfluu-éfimnmj) - But the maximum number of different n-tuples, Iq. ,..,q. I is clearly n'n-n-----n = nn Jl Jn n . £.n , as is known. hence ISA \ l 1"] Now suppose M has only one n-l block SP partition denoted IT ij = Iquj :qltq290°tqi_1:qi+1a'°oqj_qu°+19°°:an 148 and suppose 6&(qi’0) = in a 6&(qitl) = qil 5&(Qj30) = qu a 5fi(Qja1) = le for the existence of 0.. only two cases are 13 possible. Case 1 If qio # qjo. then qio e Iqi.qu and qu E Iqi,qu. Similarly if qi1 # qu, then qi1 e Iqi,qu and qjl e Iqi,qu. Case 2 If qi0 = qu’ then q.1 may be arbitrary and similarly for qi1 and qjl' (4) In both cases if 6fi(q1.0) e (qi.qj) 6M(qj,o) e (qi,qj) for 0 s {0,1} (5) (6) 149 then the maximum number of different ordered pairs reachable from (qi,qj) is four, viz. Iqu.qJ-) .011.qu .(qj .qu .(qj .quI . F - A 0 or in ‘ qu ‘ q 1 and qil = qj1 Q q define rCQO) é quIGIRO.XI = qk e Qfi ; x e 2*I and similarly for r(ql). The maximum number of different ordered pairs of states reachable from (qi,qj) is max r(q0) U r(q1) i.n since all pairs must be of the form (qk,qk). A 0 Now for in = qjO = q 5 Qfi and q11 I qjl then qil 5 Iqi’qu 9 le 5 Iqi’qu. 150 The reverse can also hold and still the maximum number of different ordered pairs of states reachable from (qi,qj) is gqi’qj)9 (qj’qigI £.n+2° (7) Finally, since n+2 is the maximum number of reach- max r(q0) + able states from the pair (qi,qj), then the reach- able states from the n-tuple, (q1,q2,..,qi,..,qj,.., qn), must be less than or equal to (n+2)'n°n-----n- n-Z /\ (8) Thus for M with no n-l block SP partitions max ISAI i nn. A M MET But if M has at least one n-l block SP partition, then max ISfiI i (n+2)-nn-2 = nn-l+2*nn-2 MET2 n < 11 o I><fl As an example of applying analytical techniques to some advantage, consider this bound as a function of k for fixed n. Let y = (n+kk-k)°nn-k then ln(y)= (n-k) ln(n) + ln(n+kk-k)- Now d ln(y) = d ln(y)-dy = 1 dv HE' J? dk’ y dk _ k — - ln(n) + l d__(n+k -k) . n+k -k dk Since dkk = kkIl+ln(k)I 312' then l.§X.= - ln(n) + kkIl+ln(k)I-l y dk (n+kR-k) 153 gz.= (n+kk-k)-nn‘k- -ln(n)+kkIl+ln(k)I-l dk (n+kk-k) and dyI= 0 when kkI1+1n(k)I-1 = ln(n). dk n+kk-k, ' , I This indicates that for smaller k (larger n-k+l block 9‘ partitions) the maximum size of the semigroup tends to be reduced for fixed n. While these bounds on Sfi are very crude, they do indicate some things which should be taken into account when searching for minimal semigroups over a class of reordered controls. As a final comment on suboptimal semigroup realizations, a particularly convenient, though not necessarily minimal, form of transition function to look for in reordering controls is a permutation-reset (PR) machine. Theorem 4.7 For any deterministic FSM control I, if for any re- . i ordering T, 16T(Q90) or I for all 0E}:T ll 0 ié,(Q.0) = q. some qu I 154 Then the semigroup accumulator has the following bound on its states < IS. _.n!+n. 1 I r Proof: F If every input is a permutation input or a reset in- put, the semigroup of state functions on Qi can be no more than the maximum number of permutations on OT , nI, plus the number of all constant states, n. C><fl This approach is also useful when applied to a subset of states in Q. Since it is easy to examine the transition function over all ET to identify all those states which transfer to at least one state in common under any input, it is a simple matter to reorder I so those states transfer to one of those common states under the same input. What- ever other transitions can be applied to reduce the size of other permutations or determine other reset inputs can further reduce the resultant semigroup. Sometimes this process re- sults in a combinatorial semigroup where there are no simple groups which are subgroups of the semigroup. As an example of this, examine the transition tables of r and its semigroup accumulator given in Figure 4.8 (a) and (b). 155 0 l 00 10 GT 0 1 58 s0 s1 $2 s3 54 123 T '50 s0 S1 S2 s3 s4 2 2 3 0,5 5 s s s s 3 1 3 l l 3 2 3 4 1,52 s2 s4 s2 s3 54 (3) 00,33 s3 s1 s2 s3 54 10,54 s4 s3 s3 $3 54 (b) Figure 4.8 FSM Control and its Combinatorial Semigroup The semigroup accumulator is the control ST with states 51’ i=0,4 and input alphabet {0,1}. S_r can, of course, serve as a common control for r in any of its three possible starting states. By examining the state func- tions defined by the input tapes, {0,1,00,10}, it is eaSily seen that no subset of states is permuted by any tape. When this occurs there are no simple groups divid- ing the semigroup of T and it is combinatorial. Contrast this with the control 11 formed by reordering state 1 in 1 above. Then S has eleven states. For 21, S has 1 2 T T 156 twenty-five states. But neither of these two reordered machines has a reset input--indicating that a good heuris- tic is to look for reorderings which uncover the largest number of reset inputs. The reordering operation may also be used to reduce the input dependency of a composite control realization. For two controls I , T and 2 = Z = m, it is gen- 1 2 T1 .ZI erally possible to reorder T1 and 12 so that a composite 1‘ realization F exists for T1, 312 such that for some skeSF: < = . < - . , 6F(sk,01j) 6r(sk,02j) , l _.j _.m ’Olj’OZj E 2F Then the transition function 6r for 5k need be defined for only m inputs instead of 2m inputs generally required in the construction. The resultant common control P appears incompletely defined but in the implementation of F the m-ary branching logic at state sk precludes the necessity to change the decision predicates mapped onto that state by any interpretations, I? . Unless the number of dif- ferent controls and/or the individual input alphabets are large, the effort in searching through all reorderings may not significantly decrease computation or run times. But it is a useful device to keep in mind when keeping the num- ber of different external procedures--identified by each 157 H . . Ii on F--to a minimum. 4.4 SubOptimal Direct Product Realizations As the example earlier in this chapter clearly indi- cates, to keep the number of states required for a direct product construction of a common control within a reason- able bound, the reordering Operation becomes an extremely valuable tool. In this section some conditions are given which have proved useful in finding smaller direct products. The concept of an SP cover will be needed. Definition 4.2 Given a deterministic FSM control, I, an SP cover, 0, on the state set QT e = B1,B2,...Bk ; Bi E.Qr, i=l,k satisfies the substitution property where for every Biee and 0e2T, there exists a Bjee such that C 6T(Bi,o) _.Bj . For exposition much of the following discussion will be limited to cyclic direct products of two semi-controls. Extensions to the general case can be made directly but only with a considerable investment in notation. 158 Definition 4.3 . . /\ A Given two semi-controls 11, 12 where 2A = EA = Z T1 T2 Qfl Iqll’q12"”qlmI " m QtzI Iq21'q22'“°qan = n' Define the set of R-minimal direct product controls AA = 1‘“ SA = / \ RI I I T1x TZI I Qr- s- ’ 6r. s. ’ i/ _T where Definition 4.4 For the direct product of two semi-controls given as in Definition 4.3, define the $2 induced cover on 91 as a set cover on ?1 induced by projecting 11Xi2 onto i2. Then 159 = .s -_<.-s O?1 {B1,B2,...Bn] , Bi Q? , 1 1 n where if = . . < -‘3 Bi [qlil’qliz’°”qlik] ’ Q11. 6 Q“ '2 1 ‘3 k then Note that as a control, 9? , is isomorphic to ?2 1 since it is the projection of the direct product machine A onto r2. Theorem 4.8 The induced covers, 9? and a? , are SP covers. 1 2 Proof: (for 0A ) ""'— T1 (1) Suppose T 5A2(qu:O) = (122 ; O 5 2 ; €121:qu € Qlt‘z and for all qli a Q? such that j 1 160 [qli.’q2i] 8 Q?lx?2 then 5?1x%2[[q11j*q21]'°] = [5€1(q11j'°)'q22]' (2) But Bi is exactly that set of qli. in (l) J Bi = fqli’} 3 j=1: IBil J and if J then 6?1 (Bi,o) = E6?l(qlij,o) .2 BQ' j=12lBil (3) Since this is true for all i, O? has the l substitution property. The proof is similar 2 D><3 The useful feature about 0? .covers is that they pro- i vide a convenient means to describe R[?1f2]. 161 Theorem 4.9 The direct product control for the reordered semi- A controls $1, T 2 (as above) 1‘“ xsfz e R[?l?2] is R-minimal iff I n _ = < ' T1 : 1 where oj is the kfz induced cover on J?l for any direct T1 h j“ < < m < < n product, Tlx r2 , 0 _,k __2 -1, and O __J _ 2 -1. Proof: Clear when it is realized that !er = Qr s . i $1 tlx $2 [><] It is apparent that the smallest direct product attainable for any two semi-controls can be achieved when one control is a homomorphic image of the other and thus must be isomorphic to some SP partition in its lattice. This fact is also readily expressible in terms of induced COVBI‘S . 162 Theorem 4.10 Let $1, ?2 be cyclic,deterministic,FSM semi-controls with Q? l' m and 0‘ |= n. If m iln, then sfz is a homomorphic 1 ‘2 image of $1 and rflx f2 8 R[Tlrz] iff I 1 [Gr : = m. T1 Proof: (1) If r . l ‘ n :=: Brew-En ;= .5 w = m . T ' . . 1-1 19. I then since T1 is cyclic Bi n Bj = ¢ (null). (2) But then 8r can be made isomorphic to some SP partition ?1 . I‘m . 1n :1 and Since NSA Or“ = 12 163 then for some we Lr (SP lattice of r?l) T1 ll? 5:2 1n. (3) The argument is reversible to show necessity. l><] Unfortunately there is no assurance that any reorder- ings exist for ?1 and?2 such that ?2 is a homomorphic image of'?l. A complete search is generally required. There is a weaker condition on the lattice structures which can sometimes be verified more easily. Theorem 4.11 Given.?l, ?2 as before, if there exists a n1, "2 such that n1 8 L ; 0:1 r:i Zm-l ; n1 = [al,a2,...ak} ; lail=bi Ecl,c2,...ck} ; Ici|=di and if n1 3 n2 as controls under the transition functions 6. , 6? where aici ; i=l,k then 164 (1) The lattice structure of rflxsfz contains both Lr and LS as sublattices. Hence it must f1 f2 contain a SP partition isomorphic to both HI and Hz. The (synchronized) projections of the direct product onto that SP partition structure identifies i=l,k disjoint blocks with no more than biicdi states in each. (2) Then k k 2 bi = m , 2 di = n i=1 i=1 and k k-l k-l k-l Z b.*d. = Z b.*d.+(m- Z b.)(n- Z d.) i=1 1 1 i=1 1 1 i=1 1 i=1 1 k-l k-l k-l = Z blxdi-mkz d -n*£ bi i=1 i=1 i=1 k-l k-l + Z ‘bik Z di+m*n i=1 i=1 165 or equivalently k k~1 k-l k-l k-l z b.*d. = -m* z d.-n*z b.+2*[( z b.)( 2 d.)] i=1 1 1 i=1 1 i=1 1 i=1 1 i=1 1 k-l k-l k-l - 2 b.* 2 d.- X b.*d. +m*n i=1 1 i=1 1 i=1 1 1 k-l k-l k-l k-l = m*n- 2 d.*(m- 2 b.)- X b.*(n- Z d.) i=1 1 i=1 1 i=1 1 i=1 1 k-l k-l k-l - X b.* Z d.- 2 b.*d. 1 1 . 1 1 i=1 i=1 i=1 < m*no D><3 IIMPR" Remark: Now the maximum value for bi*di is achieved i 1 when k=2 ; d =n-1 ; b =m-1 1 1 because k 1:1bi*d1 = m*n-b1*(n-dl)-dl*(m-bl) m*n-(nl-1)-(n2-l) m*n-(m-l)-(n-l). 166 cm the other hand, if k k-l k-l k-l 2 b.*d. = z b.*d.+(m-Z b.)(n-X d.) =1 1 1 i=1 1 1 i=1 1 i=1 1 k-l k-l = Z b.*l+(m-2 b.)*(l) . 1 . 1 i=1 1=l as expected. These are the upper and lower bounds for any two controls with common structures in their lattices. Un- k fortunately it is not necessarily true that Z bi*di and i=1 the Innnber of states in the direct product decrease as k increases between these ranges. Ihit it is sometimes the case that for any two controls there are reorderings r’r‘l, s’r‘z such that for all Ci 7! oj; O' . 1’ (Ejez = Z = L , , T1 T2 r r _ 5?1(Q.?la°i) n 6fl(Q?lan) " ‘1’ (111111) 167 and similarly S S _ 63.2(QT2901) n 6?2(Ql'2’0j) " ‘1’ (111111) If Hus is the case then there is at least one SP and Ls . A partition structure common to both.ld, 1‘1 T2 rflxsfz, if this is true for So in the direct product, IZI=2, then k=2 and the direct product must have less than m*n-(m-l)-(n-1) states. The upper bound on any rfl tightened further for a number of particular configurations of the state transition tables. One case is presented in the concluding theorem as being rather typical and might indicate an approach to further investigation and classifi- cation of these special situations. Consider the SP cover generated by the first step in the Zeiger decomposition of any semi-control,’?. Certainly the set 5? ((29,301): 5?(Qp902)} 3 '21:] = 2 is :1 SP’czover on Q . For two such semi-controls over a common input alphabet, )3 01,02 , 168 if then + a . S 6¥2(Q%2'°2) r Ga (Q? .0 1 r 1 l 2 The bound on states of controls in R[rl,r2] can sometimes be tightened if the cardinal number of the set intersection of the elements of each of the covers 5»(A9)96‘(Q") [TIQ‘rlOl I1 T102} and h) T 2 2 {6. (Q. .01). 6, (eyepj is reduced by reordering f1 and f7. That is, certain state transitions may be reversed to produce maximally disjoint SP covers of the above type. The following theorem presents a methode-for a particular form of transition table--to ac- complish this. 169 Theorem 4.12 If for the semi-control, %, the following properties hold 1) 6?(Q.ol) = Q ; lQl =11 afmmz) = Q i.e. 01,02 are permutation inputs 2) 5,(q,01) ¢ a,cq,02) ; for all qu then there exists a reordering, r, on f such that :r f = . ; 6?(Q?’°i% %_ , n even i=1,2 r 1 5fCQf301) = [3] + 1 ; n odd 9 i=1,2 where [n] is the maximum integer: n 2' Proof: A.Inethod is described herein by which a set of states ‘wilfil be: successively chosen for reordering thereby result- leg :in.21 transition table which has the desired properties. (1) 170 Choose those pairs of states with the following property: Let 6?(q.2) = }6?(q.ol),&4q.oz); then A1 = Eqi’qj} 5% (qitz) = 6.? (Qjaz) ' For every such pair (qi,qj) in A1, if their transition table entries are not identical under each input then reorder one state of the pair so that 1‘ r1 1 5.?(qi901) = 535(st01) and 1' r1 1 6? (qiaoz) = 6?(qjaoz)' The encoding of which states were reordered, r1, follows the procedure used earlier. If two states q2,q6 out of a set of eight were reordered, then (34) = (r1) = (00100010) 10 10 2 (2) 171 Now condition (2) of the hypothesis says that every state has exactly one predecessor state for both inputs 01,02. Consequently, rl A ‘ r1 5.? (A1901) - 71— : 6; (A1002) Moreover r1 6?(Q-A1.01) = 64043.02) =]Q-A1| and it is clear that only states from the set Q-Al need be considered further for possible reordering. From the set Q-A1 pick two states qi,qj such that either 1" l I‘ (a) 61(qi’ol) 1 6? (Qj :01) or r1 r1 (b) (S? ((11:02) = 61(qj,02) or 1”1 11 (C) 6f(qi901) (Sf-(qjfijz). r1 11 (Note that 6(.,2) = 6(.,Z) on Q-AlJ In case (a) no reordering is necessary. For case (b) reorder qi and qj so that 172 I‘ I‘ 2 Z 5,; ((11:01) (5? ((13:001) 1‘ 1 1 5f ((11:02) = 61(qj’02). 1 In case (c) reorder qi or qj so that 1"2 r2 5% ((11901) = (Sf (qj’ol). Here r2 = r1 + (encoding of reordered qi and/or qj) Now set A2 = A1 U {qi’qj} then r2 A 51(A2’01) = l 2' T2 l A l 61(A2202)l= 221 + 1 (3) Pick another state qk c Q-AZ Such that for some qi e AZ-Al either r7 r2 (3) H6f(qi:oz) = 61(qk’02) OT 1‘ I‘ (b) 261(q1’02) = 26f(qk’01)’ 173 In case (a) no reordering is required and r3 = r2. For case (b) reorder qk so that I‘ 1‘ I' 3 3 2 51f ((11902) 5? (qk’OZ) 181011301) where 1" =r 3 2 + (encoding of reordered qk) Now set A3 = A2 U {qu At this point A is necessarily of odd 3 cardinality'and I‘ 35% (113,01)’ = [Ad] + 1 1" 3 6?(A3’°2)| II —I “E LN L__.___3 + 1...: Note that although A3| = |A2| + l, the r cardinality of 36?(A3,oz) does not increase. r 3 But that of 6?(A3,ol) must increase since I‘ I‘ 3 3 51(qk'°1) 1 51(A2'°1) because of condition (2) in the hypothesis 174 r and because 361(A2’Ol) consists of pairs of states. Also, at this point, both 1‘ T3 3 61(A3’Ol) and 6?(A3,02) haxe exactly one unpaired state. (4) Select another state qm e Q-A3 such that for qi e AS-AZ’ either r3 r (a) 6%(qiaol) 3 6?(qm901) 0r 13 1‘3 (b) 5%(qi001) = 6%(qm902)' For case (a), r4 = r3. Otherwise reorder qm so that r4 T4 r3 6%(qi»01) = 6?(qm’°l) = 61(qm’02) r4 = r3 + (encoded reordering of qm) Then A4 = A- U {qm1’ ‘A4l 15 even and (5) 175 Since this step results in pairing the r image of qm under 45?("01) with the only r unpaired image of qi under 36%(o,ol)-- added in step (3)--the cardinality of r 46T(A4,ol) does not increase. _Now if r4 r4 (1) 5,(qm,oz) e 5,(A3,oz) then r r 4 4 6% (A4002) = 6? (A3002) also r4 A r4 6f(A4’°1) = [24] = 5?(A4,02) and the process begins again at step (2). If however, 1‘ (ii) 4 .. A 6%(A4,oz)| - I 4| + 1 then there are exactly two unpaired states in r 45?(A4,02)--one of which can be matched by returning to step (3). Steps (2),(3),(4) are iterated according to the rules above until only one state remains. 176 That is for some i, lQI-lAil = l. A quick check of the procedure reveals that if |Q| is odd, then step (3) will be the final step. Then the relationships at the end of this step, r. 1+1 - IA- l (3% (Ai+1,01)1 _ [ $411] + 1 r1+1 T i+1’02)| 6 (A ll r-—-—1 3> Ho .1. H t___s + H for A1+1 = Q, are those desired in the theorem. For IQI even, step (4) must terminate the pro- cess. But upon leaving step (3), exactly one r. unpaired state exists in both 164A1,01) and r. 16(Ai,oz). Because of condition (2) in the T hypothesis, the last state can be reordered so that its successor states match each of these. Hence the process must end with 1'. 1+1 — A' = 6fCAi+l’°l)l ’ 1.;11' with A1 = Q. I‘ . 1+1 51(A1+1'°2) C><fl 177 iIt is worth emphasizing that because of the con- ciij:icuis of the theorem and the fact that the procedure biiilchs up pairs of successor states in the images of IXi LHIdeI‘Ido?(o,X) , then at any point in the process short of the final step T. I‘- 15,(A1,01) n 1a.(Ai.oz) = ¢ When IQ] is even, this remains the case. For IQI odd, one and only one state belongs to both and r r = a,(Q.ol) n a,(Q.oz) 1 To illustrate the method the details of reordering each of two controls are summarized in the examples which follow. Example 4.3 Let a semi-control with an odd number of states be defhwd on a binary input alphabet by the transition func- tion 178 Applying the method to ? results in the sequence: after step 1: A1=iq8,q9] ; |Al| = 2 r1= (256) =(100000000) 10 2 T I b 1 = = A = L after step 2: AZ=A1 U [ql,q6} ; |A1| = 4 Z 10 r = (288) =rl+(000100000) =(10010000) 2 2 h‘ 179 r 2 - = 6% (A2,Cl)l "’ 2 121 2 T2 A 6?(A2,O’2) = 3 = l 2| + 1 after step 3: A3 = A2 U [q4] ; IA I‘ 3 6?(A3,ol)| r 35,(A3,oz)‘ = 3 = [IA3l] + 1 after step 4: A = A U £q2} ; |A4| = 6 LN II r——-—u “f; L__: + l—1 4 3 r4= (290) =r3+(000000010) =(100100010) 10 2 2 1‘4 A 6?(A4,ol) = 3 = l24| I' 4 5,(A4,oz)' = 4 = |A4I + 1 180 after step 3: A5 = A4 U [q3; ; |A5| = 7 r = (294) =r +(oooooo100) =(100100110) 5 4 10 2 Z r 55,(As,ol)’ = 4 = A5 + 1 2' 1” A 55,(A5,02)| = 4 = [I 5! after step 4: A6 A5 U £q5} ; lel = 8 16 = 15 r 6 = = [A l 6f(A6’Ol)| 4 26 r6 A 6?(A6,oz) = 5 = 26 + 1 I C after step 3: A8 = A7 U fq7g = (358) =r7+(001000000) =(101100110) 2 r 8 10 2 I‘ 8 61(A8’01)‘ = EqS’q6’q7’q8’q9] 51411 2 181 H 00 0? PD r'\ > 00 v Q N - U {C11 ’q2 ,q4 ’q5 ’q9{ 5= A8 +1 7 . and Fl) 0 Example 4.4 For an illustration of a semi-control with an even Iiumber of states, consider ? defined by (SA: q]. qz q:5 T 182 The reordered semi-control obtained from applying the method to‘? is 16 5? q1 q2 q3 = (42) = (101010) I 6 10 2 q3 q4 q5 r6 Q4 Q6 q5 6%(Q,ol) = 2,4,6 = 3 = [9| 1‘ 86 q2 q1 6530,02) = 11’3'51 = 3 191' In applying this theorem to obtain a bound on the direct product control, if two semi-controls, $1 and f2, have state transition functions which satisfy hypotheses (l) and (2), then the following is true: if ’11sz e R[T 112] Q = n . Q = m T1 T2 then < Q1? x52 —B 1 2 183 where B=[[%]+l]*([%]+11 :modd, nodd =U%]+1]*(%l :modd, neven =[%]*[[%]+1] :meven, nodd = m. * n : m even, n even. 2 2 - It is clear that the reordered controls resulting from applying the method to $1 and ?2 can be used to generate the direct product if the above bound is satisfactory. In practice the method applied to most any n-state, cyclic control over a binary alphabet produces an SP cover of the type mentioned above with no more than [ n_] + l 2 states in each of the two blocks. CHAPTER V CONCLUSIONS AND OPEN PROBLEMS This chapter presents a brief summary of the essential aspects of this dissertation and suggests possible areas for further investigation. 5.1 Summary Chapter I applied the term, algorithm, to a par- ticular binary relation on a regular set, 2*, and a set of finite outputs, Y. When this relation satis- fied certain prOperties it represents the sequential relation of a finite state machine. This model was taken as the schemata or control of a program which associated "meaning"--via an interpretation--to the states, input symbols and outputs of the control. The theorems in Section 2.1 establishing corres- pondences between program values and valuation sequen- ces provided the setting for the rest of the disser- tation: the importance and utility of a model of the control flow structure of a program. The important notion of a program-value equivalence relation led to a partial ordering, RI’ and an interpretation equiva- lence relation, , on controls. A common control was 1 184 185 one which stood in the relation RI to any one member in a class of controls such that for any interpretation on a control belonging to the class, an appropriate inter- pretation could be constructed for the common control to insure prOgram value equivalence. When the common con- trol was an H- or A-type structural realization of the control class then Theorems 2.6 and 2.7 detailed the method of constructing the appropriate interpretations. Sections 3.1 and 3.2 utilized the standard notions of SP partitions and semigroup accumulators to synthe- size an H-type common control. The composite realization of Section 3.4 illustrated how new types of controls can be synthesized using the guidelines set forth in Theorem 2.7. In Chapter IV, Theorem 4.1 demonstrated that direct product controls were also H-type realizations. The im- portant reordering transformation (Definition 4.1) was introduced and Theorem 4.2 showed that any two reorder- ings of the same control were RI related and, more impor- tantly, were value (3) equivalent via Theorem 4.3. The significance of the reordering control transformation came into focus with Theorems 4.5 and 4.6. Here bounds were established on the states of the semigroup accumu- lator of a control by restructuring the SP lattice of the control or, in the case of Theorem 4.7, striving to 186 obtain, by reordering, a permutation-reset machine. After showing how isomorphic control substructures serve to reduce a direct product control, the chapter concluded with Theorem 4.12 which provided a method by which the cardinal number of a particular SP cover is reduced. This resulted in a tighter bound on the set of R-minimal direct product controls. 5.2 Conclusions This dissertation presents a unified approach to program control analysis and synthesis. Some useful structural properties of program controls are identified and may be detected with certain finite state machine techniques. Common structural attributes so identified in a class of program controls are exploited in construc- tion theorems to fabricate a new common control structure that inherits these attributes. This synthesized control can realize the computational activities of any control in the class for each member of a set of interpretations defined on that control. The well known semigroup, direct product and homo- morphic submachine structures are examined in detail to establish confidence in the methods and approach. A new composite realization is develOped to suggest the possi- bility of creating a number of such constructs with the interpreted control model. 187 Perhaps more significantly, the approach leads to an optimization procedure which relies on a novel control transformation that preserves program value but not struc- tural properties of controls. When this transformation is applied to any of the common control constructs above, certain economies are achieved. It has become apparent that the potential usefulness of this mechanism is far from being exhausted. Some possibilities are explored in the next section. 5.3 Open Questions The examples presented in Chapters III and IV in- volving an implementation of an interpreted control utilized FORTRAN exclusively. This was to demonstrate that, in synthesizing common controls, changes required in decision predicates for non-isomorphic input alpha- bets or providing starting states or return points for each control realized by a common control can be carried out even in such an overworked language as FORTRAN. It is clear that pragmatic difficulties can be eased by em- ploying a language with richer branching facilities--APL being a good example. The possibilities of simultaneous- ly modeling the control flow of a set of algorithms pro- grammed in some procedure oriented language and, say, a search of some nonlinear data structure represented by a program implemented in a list processing language seem intriguing. FORTRAN was utilized to suggest the feasibil- 188 ity, but not the extent, of implementing the type of controls developed in the preceding text. In justifying the claim that an interpreted con- trol can be of use in the modeling, analysis and syn- thesis of programs and their structures, considerable reliance was placed on rather standard notions of ma- chine realizability. This facilitated the construction of the interpretation by way of composition mappings. The approach is a natural and common one and, not sur- prisingly, composition maps have found their way into more abstract notions of machine simulation, e.g. Herman [1968]. Are similar constructions possible for other types of machine realizations--for example machine capa- bility (Hartmanis [1966])? How can the input mapping requirement be reflected in the decision predicates mapped onto Qr by some interpretation? A satisfactory approach to this problem would permit the use of n-state universal machines to model any n-state program. On the other hand, can any of the various structural decomposition techniques suggest a more useful interpretation model so that a partial com- putation represented by a submachine of some control, T, or its semigroup accumulator has a corresponding partial 189 interpretation? Even restricted to the control and interpretation models employed in this dissertation, the reordering transformation opens up a number of interesting possi- bilities. It has been demonstrated that reordering can drastically alter program control structure while main- taining program value with correSponding changes in the decision predicates. This fact can be used advantage- ously if, say in the Zeiger decomposition of two or more controls, these controls can be reordered so as to maxi- mize the number of PR machines they have in common. Un- fortunately it does not follow that the direct product of these reordered controls is R—minimal. Can the re- ordering process be dictated somehow by the various steps in the Zeiger construction to produce R-minimal direct products? Short of exhaustive search what is the most effective method(s) of generating minimal common controls of any kind? An example of one heuristic which seems ef- fective in minimizing the direct product of two semi- controls, flez, is to minimize the direct product by searching all reorderings on $2, fixing this reordered machine and then minimizing over reorderings on ? Con- 10 tinuing in this way a path is traced on the two dimension- al grid of machine reorderings which often converges to a 190 R-minimal direct product. Typically it has been found this path has only four sides, i.e. a search was required over just 2*(2m+2n) machines where |Q?l| = m and Iszl = n. Contrast this with the worst case of 2m+n searches and there is strong motivation for developing new heuristics and, hOpefully, convergent procedures. [1969] [1962] [1968] [1964] [1965] [1966] [1966] [1968] [1958] [1958] [1969] [1967] BIBLIOGRAPHY Arbib, M.A. Theories of Abstract Automata, Prentice Hall, Englewood CIiffs, New Jersey, 1969. Armerding, G.W., FORTAB: A Decision Table Language for Scientific Computing Applications, Memorandum—RM-33UGTPR, RandgCorporation, Santa Monica,1California, September 1962. Assmus, E.F. and Florentine, J.J., "Algebraic Machine Theory and Logical Design," Algebraic Theory of Machines, Languages and Semigroups, Arbib, M}A. ed.,_AcademicTPress, Neinork, 1968} __- Elgot, C.C. and Robinson, A., "Random-Access Stored-Pro- gram Machines, An approach to Programming Languages," JACM, Vol. 11, No. 4, pp. 365-399, 1964. Harrison, M.A., Introduction to Switching and Automata Theory, McGraw-Hill,_New York,’1965. Harrison, M.A., and Gray, J.N., "The Theory of Sequential Relations," Information and Control, Vol. 9, No. 5, pp. 435-468, 196671 Hartmanis, J., and Stearns, P.E. Algebraic Structure Theory of Sequential Machines, Prentice Hall, Englewood Cliffs,“New Jersey, 1966. Herman, G.T., ”Simulation of One Abstract Computing Machine By Another," Comm. ACM., Vol. II, No. 12, pp. 802, 813, December 1968. Ianov, IU.,1., "On the Equivalence and Transformation of Program Schemes," Comm. ACM., Vol. I, pp. 8-12, October 1958. , "On Matrix Program Schemes," Comm. ACM., Vol. I, pp. 283-286, December 1958. Kaplan, D.M., "Regular Expressions and the Equivalence of Programs," Journal of Computer and Systems Sciences, Vol. 3, pp. 361-386, 1g690 Karp, R.M. and Miller, R.E., ”Parallel Program Schemata: A Mathematical Model for Parallel Computations," IEEE Con- ference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, pp. SS-6l,w1967. 191 [1966] [1968] [1967] [1966] [1968] [1965] [1963] [1965] [1967] [1962] [1964] ]l965] 192 , "Properties of a Model for Parallel Computa- tions: Determinancy, Termination, Queueing," SIAM Journal of Applied Mathematics, Vol. 14, No. 6, pp. 1390-1411, November 1966. Luconi, F.L. "Completely Functional Asynchronous Computa- tional Structures," IEEE Conference Record of the 1967 Eighth Annual Symposium on Switching and'Automata Theory, pp. 62-70, 1967. Mathers, H.W., Sedore, S.R., Sents, J.R., Sceptre: Auto— mated Digital Computer Program for Determining Responses of Electronic Circuits to Transient’thlear Radiation," Technical Report No. AFWL-TR-66-126, vol. II, FEbruary 1967. Maurer, W.D., "A Theory of Computer Instructions," Journal of the Association for Computing Machinery, Vol. 13, No. 2, pp. 226-235, April I966. , Programming: An Introduction to Computer Languages and Techniques,‘HbIden4Day,'Inc. San Francisco, 1968. Mesarovic, M.D., "New Directions in General Theory of Sys- tems," gystems and Computer Science, Hart, J.F. and Takasu, S. eds., pp. 221-231, University of Toronto Press, Toronto, Ontafio, 1965. Myhill, J., "Finite Automata, Semigroups and Simulation," Lecture Notes, University of Michigan, Ann Arbor, Michigan, 1963. Page, C.V., Equivalences Between Probabilistic Sequential Machines, Thesis, Uhiversity of Michigan, Ann Arbor, Michi- gan, I965. Patterson, M.S., Equivalence Problems in a Model of Compu- tation, Thesis, Trihity College, cambridge,'MassacHusetts, Pollack, S.L., DETAB-X: An Improved Business-Oriented Com- puter Lan ua e, Memorandum RM53273-PR, Rand Corporation, Santa Monica, California, August 1962. Rutledge, J.D., "On Ianov's Program Schemata," JACM, Vol. II, No. 1, pp. 1-9, January 1964. Windeknecht, T.G., "Concerning an Algebraic Theory of Sys- tems,” _ystems and Computer Science, Hart, J.F. and Takasu, S. eds., pp. 232-249, University of Toronto Press, Toronto, Ontaiio, 1965. 193 [1968] Zeiger, H.P., "Cascade Synthesis of Finite State Machines," Algebraic Theory of Machines Languages and Semigroups, Arbib, M}A. 3g}, Academic Press,’New York, 1968. IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII [I][I1]][[1]]I][]I]]]]]I]]]I[I]]