THE UN IV E R S I TY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department Technical Report A NOTE ON SERIES PARALLEL IRREDUCIBILITY Bernard P. Zeigler with assistance from: Department of Health, Education, and Welfare National Institutes of Health Grant No. GM-12236 Bethesda, Maryland and Department of the Navy Office of Naval Research Contract No. N00014-67-A-0181-0011 Washington, D.C. and U. S. Army Research Office (Durham) Grant No. DA-31-124-ARO-D-483 Durham, North Carolina administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR October 1969 Distribution of This Document is Unlimited

ABSTRACT A new criterion for series-parallel irreducibility is given which makes no reference to underlying semigroups but involves only series-parallel connection operations. III

A semi-automaton or transition system is a.triple- e <X,Q,M> where S,Q are finite sets (of input symbols and internal states respectively), and M: Q x X + Q is the transition function. (In the usual abuse of notation we write M for <X,Q,M>). In this note we shall characterize the semi-automata which are irreducible with respect to series-parallel decomposition. This augments the definition of Krohn and Rhodes [1] (see also Arbib's formulation in [2]), which is an essential way required the specification of output maps and thus held only for full automata i.e., machines of the form <S,Q,O,M,N> where O is the output set and N: Q + O the output function. Moreover, their definition of irreducibility for machines made direct reference to semigroups while the definition we shall give makes reference only to series-parallel connection operations. Except for changes in notation the presentation follows that of [2] Chapters 3 and 5. Let S(M) denote the semigroup of M i.e., S(M) = {M(,x): Q - Qjx s X*} where M is M extended to X*. Given a semigroup S let MS denote the semigroup transition system i.e., MS: S x S + S with MS(l,s) = s and Ms(s,s') = ss' for all s, s' c S. Note that S(MS) = S. 1 In the following we consider as usual only connected machines with specified starting state. Given transition functions Mi: Qi x X + Qi' i = 1,2, we say that M2 divides M written M2 M1 if there exist Q1 C Q1 and maps g: X2 * XZ,h: Q1 + Q2 (onto) such that

1) Q{ is closed under g(X2)* and 2) for all ql e Q{, s e X2, h(Ml(ql,g(s)) = M2(h(ql),s). n n M> Given <X,Q,M> and a positive integer n define H M = <X,Q,O M> by nnM(ql,...,qn,s) = (M(ql,s),...M(qn,s)) for all (ql,...,qn,s) Qn x X. HnM represents n copies of machine M (possibly in different states) which are run in parallel and are fed the same input symbol. Definition: IM T-divides M1, M21 M1 if there is a positive integer n such that M21 nM. We remark that division, and n-division are transitive relations. M mutually iT-dividesM, M M if M | M and M M. '-"~~2 1'2 W 1 2 ITM 1 I 2 We require the following statements: 1. M2IM1 implies S(M2) IS(M1).2 2. S(M2)JS(M1) implies M2IMS(M) 3. M IS(M)1 4. S(eM) = S(M) Proofs may be found in Chapter 1 of [4]. Suffice to say that (1) and (2) are well-known; (3) is a slight extension of Fact 2.14b, Chapter 5 of [3]. For (4) we note that flnM(ql,..,qn,x) = (M(q1,x),...,M(qn,x)) so examining the Myhill equivalences relations: x y ~=for all (ql,q2,2 00,qY n Q?1M(ql,.x) ~nM(ql;...,qn,Y).#for all q e Q, M4(q,x) = M(q,y) Be- x = y.

So S(1 nM) = X*I = = X* I = S(M). 11nM M Proposition 1: S(M2) IS(M1) if, and only if, M211M1 Proof: Assume S(M2) IS(M1) Then from (2),M2IMS(M ) Also from (3) MS(M) 1TM1 so by transitivity M2 IM1. Conversely assume M21TM1. Ten for some n, M2ln1nM so by (1) S(M2) Is(nIM1). Recognizing that S(1nM1) - S(M1) from (4) completes the proof. We see that Proposition l.allows re-interpretation of semigroup division in terms of T-division. This is not true for ordinary division-to make the converse of (1) hold, output maps have to be added to the semigroups as in Theorem 7.3.10 of [2]. The best that we can get from (1) and (2) is 5. S(M2)/S(M1) if, and only if, M2 MS(M). An interesting consequence of Proposition 1 is Corollary 2: M1 _ M2 if, and only if, S(M1) - S(M2). Proof: Apply Proposition 1 twice. The standard definitions of irreducibility are: a) A semigroup S is irreducible if whenever SIS2 xz S1 then SIS2 or SIS1. (Here S2 xz S.1 is a semidirect product of S1 by S2 with connecting map Z) b) A machine M is irreducible if whenever MIM2 xz M1 then MIM2 or MIM1. (Here M2 xz M1 is the series-parallel cascade of M1 followed by M2 with connecting map Z.) c) A machine M is s-irreducible if whenever MIM2 xz M1 then MIMS(M2) or MIMS(M2)

We add the definition: d) A machine M is '-irreducible if whenever MIM2 xz M1 then MI,M2 or MIjM1. Theorems 8.3.6, 8.3.7 page 4 of [2] state that M is s-irreducible if, and only if, S(M) is irreducible. On the other hand, while M is irreducible implies S(M) is irreducible, the converse does not hold.3 Based on Proposition 1 we can now show that the equivalence does hold for t-irreducibility. Theorem 3: M is t-irreducible, if and only if, M is s-irreducible. Proof: M is '-irreducible - if MIM2 xz M1 then Ml,,M2 or MIM14= if MIM2 x M1 then S(M) IS(M2) or S(M) jS(M1) (from Proposition 1) =if MIM2 x M1 then MIMS(M) or MIM S0 (from (5)) =M is s-irreducible. (M2) In conclusion, we have seen that the irreducibles are strictly included in the s-irreducibles which are co-extensive with the I-irreducibles. What this says is that although a machine M which is s-irreducible but not irreducible has a series-parallel decomposition into machines M1, M2 such that neither M1nor M2 can simulate M, still it must be that by taking a suitable number of copies of either M1 or M2 we can simulate M, i.e., M M1 of MIM. Finally we note that Theorem 3 enables us to relate the s-irreducible machines given by the Krohn-Rhodes Theory (the simple group and unit actions) entirely to machine decomposition operations without reference to semigroup concepts.

FOOTNOTES 1S1 is the smallest monoid containing S. 2For semigroups Si, i = 1,2, SllS2 if S1 is a homomorphic image of a sub-semigroup of S2 3Actually, there are proved for full machines but can easily be shown to be true for semiautomata.

REFERENCES 1. Krohn, K. B. and J. L. Rhodes "Algebraic Theory of Machines", Mathematical Theory of Automata, p. 371, Polytechnic Press, 1963. 2. Kalman, R. E., P. L. Falb and M. A. Arbib Topics in Mathematical Systems Theory, Chapters 7-8, McGraw-Hill, 1969. 3. Arbib, M. A. Algebraic Theory of Machines, Languages and SemiGroups, pp. 41-46, Academic Press, 1968. 4. Zeigler, B. P. "On the Feedback Complexity of Automata", University of Michigan Technical Report No. 08226-6-T, Ph.D. Dissertation, Computer and Communication Sciences Department, Ann Arbor, Michigan, 1968.

UTICT ASSITIEL... aunty -Classi fication DOCUMENT CONTROL DATA,- R&D (Security claeeitlcation of title, body of abatract and Indexing annotation must be entered when the overall report ia cladlilled) I ORIGINATING ACTIVITY (Corporate author) z2a REPORT SECURITY e LASgIOA TIMlt LOGIC OF COMPUTERS GROUP Unclassified The University of Michigan 2b. GRtouP Ann Arbor, Michigan 3. REPORT TITLE A NOTE ON SERIES PARALLEL IRREDUCIBILITY 4. DESCRIPTIVE NOTES (Type of report and lncfuelve datea) Technical Report S. AUTHOR(S) (Lest name, tint name, tnitial) Bernard Phillip Zeigler 6. REPORT DATE 7*. TOTAL NO. OF PAGES 7b. NO. OFP REP October 1969 10 4 8a. CONTRACT OR GRANT NO. 94. ORIGINATOR'S REPORT NUMBER(S) DA-3 1 -124-ARO-D-483 b. PROJECT NO. C. |. 0, T R Rt PORoT NO (S) (Any other number that, may be aeal;4ed (th reporot d. 10. A V A IL ABILITY/LIMITAtiON NOTICES Distribution of This Document is Unlimited. 11. SUPPLEMENTARY NOTES 1'. SPONSORING MILITARY ACTIVITY U.S. Army Research Office (Durham) Durham, North Carolina 13. ABSTRACT A new criterion for series-parallel irreducibility is given which makes no reference to underlying semigroups but involves only series-parallel connection operations. DD 1 * JAN 4, 1473 UNCLASSIFIED Security Classification 9

_ INLTASS TLT FED Security Classification 14. LINK A LINK B LINK C KEY WORDS. ROLE WT ROLE WT ROLE WT INSTRUCTIONS 1. ORIGINATING ACTIVITY: Enter the name and address imposed by security classification, using standard statements of the contractor, subcontractor, grantee, Department of De- such as: fense activity or other organization (corporate author) issuing (1) "Qualified requesters may obtain copies of this the report. report from DDC." 2a. REPORT SECURITY CLASSIFICATION: Enter the over- (2) "Foreign announcement and dissemination of this all security classification of the report. Indicate whether reign anno uncement and dis semination of this "Restricted Data" is included Marking is to be in accord-report by DDC is not authorized" ance with appropriate security regulations. (3) "U. S. Government agencies may obtain copies of this report directly from DDC. Other qualified DDC 2b. GROUP: Automatic downgrading is specified in DoD Di- users shall request through rective 5200. 10 and Armed Forces Industrial Manual. Enter the group number. Also, when applicable, show that optional.. markings have been used for Group 3 and Group 4 as author- (4) "U. S. military agencies may obtain copies of this ized. report directly from DDC Other qualified users 3, REPORT TITLE: Enter the complete report title in all shall request through capital letters. Titles in all cases should be unclassified.,, If a meaningful title cannot be selected without classification, show title classification in all capitals in parenthesis (5) "All distribution of this report is controlled. Qualimmediately following the title. ified DDC users shall request through 4. DESCRIPTIVE NOTES: If appropriate, enter the type of ___, report, e.g., interim, progress, summary, annual, or final. If the report has been furnished to the Office of Technical Give the inclusive dates when a specific reporting period is Services, Department of Commerce, for sale to the public, indicovered. cate this fact and enter the price, if known. 5. AUTHOR(S): Enter the name(s) of author(s) as shown on 11. SUPPLEMENTARY NOTES: Use for additional explanaor in the report. Enter tast name, first name, middle initial. tory notes, If:r.litary, show rank and branch of service. The name of the principal author is an absolute minimum requirement. 12. SPONSORING MILITARY ACTIVITY: Enter the name of the departmental project office or laboratory sponsoring (pay6. REPORT DATE. Enter the date of the report as day, ing for) the research and development. Include address. month, year; or month, year. If more than one date appears on the report, use date of publication. 13. ABSTRACT: Enter an abstract giving a brief and factual 7a. TOTAL NUMBER OF PAGES: The total page count 0 summary of the document indicative of the report, even though s f7a. TOTAL NUMBER OF PAGES: pThe total page count it may also appear elsewhere in the body of the technical reshould follow normal pagination procedures, i.e., enter the port. If additional space is required, a continuation sheet shall number of pages containing information. be attached. 7b. NUMBER OF REFERENCES: Enter the total number of I It is highly desirable that the abstract of classified reports references cited in the report. be unclassified. Each.paragraph of the abstract shall end with 8a. CONTRACT OR GRANT NUMBER: If appropriate, enter an indication of the military security classification of the inthe applicable number of the contract or grant under which formation in the paragraph, represented as (TS). (S), (C). or (U). the report was written. There is no limitation on the length of the abstract. How8b, 8c, & 8d. PROJECT NUMBER: Enter the appropriate ever, the suggested length is from 150 to 225 words. military department identification, such as project number, subproject number, system numbers, task number, etc. 14. KEY WORDS: Key words are technically meaningful terms or short phrases that characterize a report and may be used as 9a. ORIGINATOR'S REPORT NUMBER(S): Enter the offi- index entries for cataloging the report. Key words must be cial report number by which the document will be identified selected so that no security classification is required. Identiand controlled by the originating activity. This number must fiers, such as equipment model designation, trade name, military be unique to this report. project code name, geographic location, may be used as key 9b. OTHER REPORT NUMBER(S): If the report has been words but will be followed by an indication of technical conassigned any other report numbers (either by the originator text. The assignment of links, rules, and weights is optional. or by the eponsor), also enter this number(s). 10. AVAILABILITY/LIMITATION NOTICES: Enter any limitations on further dissemination of the report, other than those UNCLASSIFIED Security Classification 10