Finite switchboard state machines and fuzzy finite switchboard state machines (有限スイッチボード・ステート・マシンとファジー有限スイッチボード・ステート・マシン

全文

(1)Fini七e swi七chboard s七a七e machines. and fuzzy finite switchboard state machines 2003年. 佐藤康浩. 兵庫教育大学大学院連合学校教育学研究科自然系教育専攻. 上越教育大学配属佐藤康浩.

(2) Conte総ts. Preface. II. 1．L. 至難もr◎d難etl◎n. l．2．. H◎m・m◎罫歯自m. 13．. CeveriRg＄ and Products. 1．4．. Direcもprod魏cts and Wreathひrod疑cts. 2．. Swiもchわoard sもaもe machines. 2．1．. Switchboard state machines and switchboard transformation semigrolips. 2．2．. Restricted cascade products. 2．3．. Cartesian compositioRs. 3．. F犠脇y伽ite sw玉tchboard state machiRes. 3．1．. I難もroduct三〇勲. 3．2．. Semlgroups of Fuzzy Finite Switchboard State Machines. 3．3．. Homomorphisms. 33. Finiもe sもaもe machines. 1 75 51 9← 02 n∠2 9 合δ阿イ Oド003 04 F F∂5桝‘肺‘ ■ 1. 1．. 89. Refereft ces. 1.

(3) Pref臨ce. In the 20th century， comput・er sc｝ences have been developing and in− fiueRclitg varieus fields of many scienees． ln recent years， studies from a. nexv view of social affairs have been demanded whlle the complication of. human ＄oclety has grown． ln the meantime the theory of machiRes has been growing by mefi of abilitles， for instaBce， Claude E・｝wood ShaRnon，. Alan Mathison TuriRg， Jehn von Neumann． The aim of so−called system tkeor：y’ was to build up ideas and tools of varlous systems such as elec一もr｝cal e貧g至強8er圭ng， phys重。茎ogヲラもheoret三ca茎bio墨◎gy， sociology，1ingu董stics・. The theory of lnformation， the theory ef contrel， the theory of finite. state machines and the theory of fuzzy systems can be regarded as some of the essentlal parts of system theory． The areas ef mathematics that. ls mostiy used in these theories are probabll；ty theories and modern alg；ebra、． The ma孟）hema’も董ca渓宅oo豆s tha・t is of most use fbr th董s p陣aper 三s. modern algebra． For some hundred years， algebra has developed in a lot of directions． But the gyowiRg of theory of machines has provided. human beings with new motivatlon for the devel◎pmenも。縁lgebr昂． Thus W．M．L．｝E｛olcombe ［1］ upon whlch Lhe former part of this paper is based. deals with dlscusslons on the algebralc realm of automata theory．. Chapter 1 begins with some of elementary material eoncerning the ￡heory ef algebraic automata theory． After introduclng the ceitcept of state machiRe at first， semigroups of state machine are formed on sets of state． Thus transformatieR sernigroups are associated with the state. machines by the semigroups of state machlkes． State ma￡hine hemo− morphisms leads to quotie＃es of ＄tate machiRe， and so to transforination. h◎mom◎r轟sms． When the functional properもies of the漁te machines are discussed， the concept of coKreriRg 1＄ more usefukhan that of homo−. morph三s澱．. 互至.

(4) For example， trapsformatlen semigroups ef A state machiRes are able. to be covered by transformatien semigrollps of B state machines if A state machlne＄ are covered by B stute machines． Product of state ma−. chlnes aRd of transformation semigroup can preduce malty iBteresting properties in relatlon te coverings． Some of covering theorerns calt be rewrittelt by the cencept of homomorphism． Their exarr｝p｝es aye picked up to reveal the usefulness of the algebraic automata theory Some kind of products that are dealt with in ￡his paper are the most importaRt. when we discuss finite state machiRes aRd transformatioA semigroups． We define rest，rlcted dire￡t prodlicts， full direct products， cascade prod−. ucts afid wreath products with respect to fiRlte state machines and trans−. formation semigroups． As te wreath products， it is knowR that wrehth. products of two transformation semigroups are taransformation seml− groups． And transfermatlon semlgrenps of wreath product of two klnds of finl￡e state ma￡hlnes are able to be cevered by wreath preducts of two klnds of ￡ransformation semlgroups of state machines． As to direct prodllcts， traBsformatiofi semigroups of full direct product of two klRds ef finite state machines are able to be covered by full direct products of. two kinds of transformation semigroups of state machines． As to rela−. tions between ful｝ direct products and wreath products， transfermation. semigro叩s of翻dlrecもpr◎duct of two kinds of・finite state machines are able te be cuvered by wreaeh products of two klitds of transformation. semigroups of state machines．. Chapter 2 examines some elementary properties of switchboard state. machines and switchboard transformatloit semigrollps． After defining switchboard state machines by binding the concept of swltcking state machlnes and commutative state machines toge￡her， switchboard trans− formation semigroups are defined the same．. III.

(5) Examples switchboard state machines， switching st＆te ma￡hines aRd coramutative state rnachines are picked up． lt ls revealed that transfor−. mation semlgroups of swit・chboard state machines are switchboard trans−. formatlon sernigroups． By introducing swltching relatiolls on switch− board state machlnes， switcklng classes are defined and quotients ef. Sもaもe鵬Chine led by徳e SWitChi難g ClaSSe曲eCOme SWitchb◎ard S捻te machines， too． We call the quotlents switchboard state machines for small slgma ln large slgma． Switchboard state machines for smail sigma in large sigma can be covered by the swkchboard state machines．. We define restrleted cascade produc￡s between two complete state. machlnes and presept some examples of restricted cascade products．. Through semigroup epimorphisms from one switchboard state machlRe te anether switchboard state mackines， it reveuled that cascade prodllcts. of the two swltchboard state machlftes beiRg switchboard state machines are equal te the ￡wo state inachines being switchboard state machines．. By counter examples， cascade products of traBsformation semigroups of twe state machines cannot be covered by transfoTmation semigroups ef cascade products of two state machiRes． However oR an special condi− tions， transfermation semlgroups of restricted cascade preducts of ＄tate. machiBes and switchboard・ state machlnes are isomorphlc to restTicted. cascade prodllcts of transformatlon semigroups of state machines and trallsformatioft semigroups of switchboard state fnachines． This theo− rem produces some corollaries witk re＄pect to the other products．. We study cartesian compositions ef state machines． After presenting some examples of cartesian eompos｝tleB＄ of state machines， it is revealed. that carteslan composltiens of switchboard state machines are switch− board state machines， too． And we examiRe relatlens among cartesian products and the oigher products． All Lemmas and Propositiens in Chap− ter 2 are due to ［11］．. 至V.

(6) Qulte a loRg tirr｝e after L．A．Zadeh in￡roducing the concept of fuzzy sets， the field of fgzzy sciences was regarded as some exotic field of re−. search． But the resent sucee＄s wlth coitsumer products involving fuzzy tools causes a growlitg interest of not only mathematiclaRs but also eR− glneers．. Chapter 3 iRtroduces the concept of fuzzy finite state ma￡hlnes and fuzzy transformation semlgrollps at first． After some example＄ of fuzzy. 舳lte sもate難achines a難d fuzzy transformation semigr◎ups， s◎me con− cepts of homornorphism of fuzzy finlte state machines and fuzzy trans−. ferm＆tion semlgreups are introdgced． Among them， strong homemgr− phisms are most important． For example， there exists an isomorphism from some quotients of A fuzzy finite state machines to B fuzz．v finlte. state machines if there exists an oRte ＄trong homomorphism from A fuzzy finite state ii｝achines to B fuzzy finite state machlfies．. “Je introduce the concept of fuzzy finlte state machines and fuzzy tran＄foTmatioR semigrolips． Those are some klnds of fuzzillzation of fi− nite state machines and transforma￡・ion semlgroups． The ldea of switch−. ing homomorphism is introduced， and sorne propertles which are aRalo− gous to those obtained by Malik， ModeTson hnd Sen ［10］ are examined． Ail Lemmas and Propositions in Chapter 3 are due to ［12］．. V.

(7) Abstraet This paper deals wlth swlt，chboard state machines whlch are speclal− ized finite state machines， and deals with fuzzy finite switchbeard sta￡e machines which are fuzzillzatioRs of flizzy finite state machines．［1］he. 徹st ha｝f◎｛もhis paper is幡ed叩on W．M．L．Holc◎mbe［1］， which de＆ls vvTith discussions on the algebralc realm ef auteu｝ata theory． In regard to traBsformatioB semlgroups， see the book ［5］．. After lntroducing the concept of state machine at fust， semigroups of. state machlRe are formed on sets of state． rl”hus transformatlon seml− groups are associated with the state machines by the semigroups of state. machlnes． State machiRe homomorphisms leads to quotients of state ma−. chlne， and so to transformation homomorphisms． “・Jhen the funetiollal properties of the state machines are discussed， the concept ’ 盾?@ceverlRg ls more usefui than that of homomorphism． Prod＃cts. of state machines and of transformation semigroups can produce many lnterestlng properties iR relation to coverings． rl“he second half of this paper deals wi￡h restricted types of finite state. machines． Switchboard stat・e machiRes and switchboard transformatleft semigroup are introduced at first． Some types of products are charac− terized by these concepts． New i＞rpe of products are contaiRed in those． Asも・these盤ew types・f pr・ducts， some properもies ln relaも1◎難も。 sもaもe. machines and transfermatien semlgroups are dlscussed． Last・ly， the concept of fuzzy finite switchboard state machines and. fuzzy transformation semigroups are introdllced． The idea of switching homomorphlsrr｝ ls IRtroduced， and some propertles which are aRalogous ￡o those obtained by Malik， Mordeson aRd SeR ［lg］ are examined． Their examples are plcked ljp ￡o reveal the usefulness of the algebralc. ＆uも◎m庶綴eory．. 1． Finite sSate machines 1．1． 1】【1もr｛）d騒。もio】a. The theory of autemat，a or｝ginated in some former theories． They con一. 捻1捻題etぬe◎ry o罫Turing machine， computer and Klee難，s癒eory． The theory of automata has deve｝oped ln the lasttwenPy years， and the math−. ematlcal theorles has been growing along together． One of them is the algebraic antomata theory． The ￡heory ef machines has been applied to. 1.

(8) computer systems， lingulstlcs， biology， psychology， biochemistry， sociol一一〇gyラeも。．1㌧歪◎s￡◎f＆1奎，もheもheory嚢sing a韮gebraic techniques has deve重ope（墨. reCently。頚搬翻y SyStemS enVirOnmental StimUli Cha嚢ge◎rganismS．、へ絶 caR deem many of interactionin those as dlscrete and fi ni￡e wklle ＄ome of. those behavier are contlnuous and lwhRlte． Seme kinds of slmpie systems are called state machiRes．［1］hese have strong relatlon to transformatioR. semigroups． IR regard io transformatioA semigroups， varlous impertant reslilts have ever been held including The Covering Lemma paper ［3］． Te think systems simply， we identify the set 〈［？ vv’ith intern．ai states. a難dideallze environmental inp嚢もt・be魏郷吻hαbetΣ〕．恥define a partial function F ： Q × X 一〉 q iit such a way that F（（g，a））＝＝ g’ where. 9∈Q，σ∈Σan（韮41Sもhe res滋もof upplylngσも。 the sysもem in sもaもe g． A state 7nachin，e ls a trlple M ＝（（？，X， F） where （［？ and X are finl￡e. sets and F is a partial function F ： Q × ￡一 q． We comslder the set X“ of a｝1 words in the alphabet X， define a relation A」 oR Yk−」一＋一 by. α∼β⑬凡＝恥 where a，5 G X’． M ＝（（？，：！］，」17） is called com，plete if the partial functloR 1” ：〈［？ ×X 一（？. ls a functien．. ∼三Sa COngrUenCe relati・n， S・We C・nStrUCt th閃U・tlent Semigr・Up. Σ＋／∼・・d・・llit亀h…吻r・拶φん・・t・t・・m・・ん厩砿d…t・dS（A4）．［1］he elerr｝eRts of S（M） are equiva，lence ciasses ［dv］，a G X＋． A ls cailed. the n・鴛tg鍵。爆satisfyin9αA＝：Aαmeα負）rα∈Σ一←． De§難eもhe．かεε窺ono掘 senerated by the set X by ￡＊ rm X＋ u ｛A｝．. Almost all Defini￡ions， Theorems and Proposltions in this chapter’ are due to NV．M．llelcombe ［1］．. ffxamp ges （i） Some simple cases are where 1（［？i ＝ 2 aitd 1￡i ＝： 1’． Let M ＝（C？， X， F）. be a complete state machine where C？＝｛O， 1｝ and ￡＝｛ff｝．（a）. F σ. 0. 1. 0. 1. （b）. 2.

(9) F σ. 0. 1. 1. 1. 0. 1. （c）. ◎. F σ. o. （d）. F σ. 0. 1. 1. o. （2） A little coMlicated cases are where 1〈？1 ＝ 2 and 1￡1 ＝ 2． Let. M ＝＝（（［？，￡，F） be a compiete state machlne where Q ：｛O，1｝ and X＝｛q T｝．（a）. ◎. F. 1. σ. 0. 1. ア. 1. 1. 0. 1. （b）. ◎. F σ. 1. 0. 0. o. 1. σ. 0. 1. τ. 1. o. 0. 1. 1. 1. 0. 0. ア. ︶︵ C. F. （d）. F σ. T. 3.

(10) ︶︵ e. F. 0. 1. 1. 1. 1. 0. o. 1. σ. 0. 0. γ. 1. 0. σ τ. ︶︵ f. F. （3） ARo￡her llttle cemlicated cases are where 1〈［？1 ＝ 3 aRd 1：1 ： 1， Let M ＝（q，￡，F） be a complete state machlne where （［？＝｛O， 1，2｝ and x ：｛if｝．（a）. F σ. 0. 1. 2. 0. 1. 2. 0. 1. 2. 0. 2. 1. 0. 1. 2. G. 0. 1. 0. 1. 2. 0. 1. 0. （b）. F σ. （c）. F σ. （d）. F σ. （e）. ！. σ. o ◎. F. 1. 2 1. 4.

(11) And so forih．．All kinds of state machines where 1（［？i ：3，［￡1 ＝1 are. 2Z 1．2． Hemoxx｝orpki＄ms Mkiee state mach｝nes have strong relatlon to transformatlon seml− groups． Soiv｝e properties are dealt vv’ith through the coitcept｝oA’ gf ho−. momorphlsm hefe． Admissible relatlons are necessary and suMcieRt coR− ditions ￡e ceRstruct quotient state machines and quotlent transforma− tioll semlgroups． Tkere exists a sort of homomorphism theerem 5etween state ma￡hiRes aRd their quotlents， as well as between transformation sem逡；ro難茎）s ai｝d t｝｝e量r quotients．. PreposiSion f．2．！ Let M ＝（C？，X， F’） be a st，ate mashine and 〈F（A，1）〉 the subsemlgromp ef. PF（q） generated by ｛F． lff G X｝， then 〈F（M）〉！1 S（M）：X’／ rv．. F賦herm◎re S侮）玉s謡難ite semlgr・up．. Pro（ゾ De§捻eθ：Σ＋／∼→＜F（！if）＞byθ（［α］）＝Fa fbr∀α∈Σ＋， Clearly e ls vv’ell−defiited． Let 7 E E ＋． As we can indlcate f？＝： Fty for VF E 〈F（！kD＞， there exlsts ［Af］ G kY．＋／ N． Hence e is serjective．. Let・e（［α］）・S個）， Then凡＝鰯⇔［α］；［β］・Renceθis lnjectlve． Let ［ce］，［，Sj G X＋／一v． Then. g（［or］［6］）＝＝ FaG. ・・凡乃＝ e（［dv］）0（L3］）．. Hence e ls a homomorphism． Slnce 1｛［？1 〈（×）， clearly IPIF（C2）i 〈 oc． HeRce IS（M）1 S IPF（（？）1 〈 oc．. Defin・itien 2．2．2. Let （？ be a fiklte set， S a finite semigroup， and a partial function A ：（［？ × S 一一〉〈［？ aR action・ of S on （［1｝ satlsfying two conditions ：. （三） λ（λ（9ヲ3）ラ5玉）＝λ（9，35玉） fbr all g∈（；∼；5，5王∈5・. 5.

(12) （ii） A（g， s）＝： A（g，＄i ）， Vg E （［？ lmplies s＝ si where s， si ff S．. 至も is 簸S芝ユa浬 to write λ（9，s） as g3 for 9 ∈ （∼ラε ∈i 5．. （Q，5）with this acti◎n A 3S called a transfer7nati・n・se吻r・ttP．. かεfinition f，2，3. Let M ：（C？，X， F） be a sute machine． we call a tTamsformatlon semY group （（？， S（M）） the transfor，7zation semigro up of M denetlRg by TS（kl）. Define the transformation moneid TS（M）i ：（〈？，S（M）i）．. Exgmples Let M ur （〈？，X，F） be a cemplete state machine where ｛［？＝｛a，b｝ and ：：｛ff， 7一， P｝．. う. α. F. α. α. σ α. 6. γ. ρ. 6. 磁. Then ［1］S（M） is as follows．. α. ［ρ］. 6. α. み. ［τ］. α. α ［στ］. δ. α. λ ［σ］. 6. 6. And the multiplicatlon table of S（tW） ls as follows．. ［σア］［σ︼. ［σ］［σ］. 1σア］. ［σ］. ［炉］. 回. ［σ］. ［ρ］. ［σ］. ［ア］. ［ρ］. ［ア］［σ］. ［σア］. 回. ［ア］. ＊. ［σ］. ［σγ］. ［σ・］. 回回［σ7］. As S（2・V） ls a monoid， TS（M） ls a traRsformktieft moRoid．. 6.

(13) Definition 1．2．4. Leも鯉’＝（e，z， F）and八f1＝（（∼ノ，Σ’ラF’）be state mach｝Res． Let ew ：（［？一一〉（［？’， fi ： E］一￡’ be mapplng＄ sllch that. tv（gFa） Q （a（g））E6（a）. 薮）ra難y9∈（∼，σ∈Σ．. The pair （a，，3） is called a state machine homomorphism from M to iiVi’ and writ￡eR （cy，，g）：Aif 一一〉 A4’．. If ctr aRd ，3 are both one−owae mappings theR （（M，5） ls called a monomor−. phism and if （N and 5 are both ente mapplngs then （a，5） is called afi. epimorphis7？z． An i＄omorphisrn of state machines is both a monomor− p嬉sm altd an eplmorphism， in this case wriももe貧M霊IMノ．. Pefinitien ？．2．5. 1f A ：（Q，S）A’＝：（q’， S’）are甑難sf◎rmatl・n semlgr・ups，ノ：q→9’. is a mapping and g：5→Ss包se麟gro叩homomorphism， then the palr. （f，g）issa三dt・・bea伽吻・m・伽5e吻r・塑ん・m・窺・繊細fr・mA t（｝A／if ア（｛∼ε）⊆∫（g）9（s）. fer all g E Q，s E S， written （f， g）： A 一〉 A’． Define menemorphism，. epimorphism， isomorphism ef （f， g）： A 一 A’ in the same way as state machiRes． Denote lsomorphism （f， g）： A 一〉 A’ by A bl A’．. Tゐeo 7re m ノ．2．6. Let ノレノ＝（9，Σ， F） aRd ノレfタ＝（（；｝tラΣ’，F’） be complete state 獄a・chiRes．. Let （（y，5）： M 一一〉 M’ a homomorphism with c￥ oRto． Theit there exists. a homomorphism （fcr，ge）： TS（M）一一〉 TS（M’）．. Preef Define f．：（？一〉 Q’ by f．＝a． Put S＝ S（M） and 5㌧S（・M’）。L・t∀s G S， then therεexisもs妊Σ＋・uch that・s＝同。 Now put a ＝＝ cria2 一・・ffn， ffi E E］， i＝ 1，2，．．．，n. aRdβ（の＝β（σ1）β（σ2）… β（σn）∈（Σソ）＋． Define gβ（s）篇［β（α）］’ξss． Let s E S． Plit s＝：［b］， b E X＋，b ： Ti T2 … rm， Ti G X， i ww一 1， 2i … ，m・. Let同篇［b］， then娼篇暢｛br∀9∈q＿（＊）牌イ.

(14) SiBce ｛［M is onto， there exists g G （［？ such that q’ ： cv（q） for Vq’ G （？’．. Hence g’E6＠：（a（g））Fb（．），. ・ giE6（b）＝：（cv（g））iF16（b）・ By （＊）， or（gF．）：a（gf？b）． Since （a，P） is a homomerphisTy｝，. ew（gF．）＝（a（g））F6（．）：（cM（q））ny6（b）・. H・ece 4E6（。）＝9’％（の・th・t i・β（の∼’β（b）・Tke・e勧・e gβ・5→s’ i・ we11．（玉e且ned． Lee g （g （？ aRd s （1 S， where s＝［a］， a （！ X＋．［1］hen. ん＝吻s）：α（9．乾）＝（ce（g））F］E（a）. ：ん（の［β（a）γ. 嵩ん（9）9β（s）．. Hence （f．，g，3） ls a homomorphism． M Theorem ！．2．7. Let A ＝（q，S） be a transformation semigrollp． Then TS（SM（A））霊湾．. Proof Put SM（A）＝：（｛1？，S， jl？） aRd K ＝〈Fi（SM（A））〉． By Propo−. sltion 2．1， K tw S， se there exist・s an isomorphism e ： S 一一〉 K， where e（s）： F，，se S．. Now eensider a pair ef mappings （IQ，e）： A 一 TS（SM（A））， where TS（SM（．底））＝（（∼亨K’）・The盆 lq（gs）＝＝ gs ：gF，＝ lg（g）g（s），. Vg e （［？， Vs E S． Hence （lq，e） is a transformatioR semlgrettp lsomor− phl＄盟．【コ. Theorem f．2．8. LeもM＝（Q，ΣニヲF）be a state macぬi難e． Then崩ere exists a staもe machine. monomorphism （or，，3）： M 一 SM（TS（M））．. 8.

(15) Proof We can ind｝cate SM（TS（M））＝：＠，S（M），F）． DefiRe or ： C？一一〉（［1｝ by a ＝ IQ， and define 6 ： X 一一一〉 S（M） by rs（o）＝［ff］， u e ：．. 覧e飢董ear童yα鼠ndβare・ne一・ne mapplng＄． Le￡ g G （？ aRd cr G X．［1］hen. cy（gE．）＝ gF．. ＝嬬】＝（α（9））％（の・. Hence （or， rs） is a state machine ry｝oRemerphism．. 日. 1）eプiηitionノ，2，9 Let M ＝（（？，：［］， iF） be a state machine．. A relation R on q 1＄ cal｝ed gdmissible if and only if （i） R is an equiva｝ence relation，（1三）（gF．）R（91罵） for Vg， gi G （［？， Vff E ￡ such that gRgi， g．F． 7！1 ￠， giF． pt ￠．. ，Propesition f．2． fg Let M ＝＝（（［？，￡， F） be a state machiRe．. Let R be an admisslble relation oR （？， und Ti ＝＝｛Hi｝iE」 a partition on （［？ indllced by R． Define. ffi Fa ＝｛gFa l g E Hi｝. 飴r∀疏臼，∀σ∈Σ・The難もhere existsブσsuch that瓦瑞⊆称 Proof Let gi G ffi． Then there exists ］’ G J such that giF．＝ g2 e llj・． Letg E Hi． ’Then gRgi．. Let g瑞≠のand g鵡≠の． Then（鳴）R（91 Fa）， becau＄e・R・is・admis− si ble． Hence gFff G Hj， so ffi Fa ［ Hj・. LeもgFa＝の◎r 91∫F．＝の・The貧ffi＝の． He識ce HiF．⊆∫ち．巳. 五）〔面癖廊on！，2．！！. Let M ＝（（［？，￡， F） be a state ma￡h；ne．. A partitloft r ＝｛lli｝ifff of q is called adTnissible if and oitly lf. there exlsもsブ∈1such t・hat ffiFa⊆瑞f・r∀乞∈∫，∀旺E，・r瓦島．：の．. 9.

(16) Propesition 1．2． f 2. Let 2iver ：（q，：， F） be a complete state machine． Then g ； 1 × ￡一 1 ls a，f鱗難cti◎鍛．. Preof Since M is ￡omplete， gF． E （［？， g17．＃ e for Vg E （［？， Vg G X．. TheR ffiF． pt e for Vi G 1． Now a’ssume HiF． g H」 and HiF． g llk，］’ 1 k． Then ff」 n Hk X ￠． This contradicts with that 7r ls a partition on（？． Henceゴ＝勘．［コ. 1）頃癖捻。箆？．2．ノ3. Let A ＝（（？，S） be a tramsformatien semigroup． A reiatien R oR （2？ is called admissible if and oRly if （i） R is all eqglvalence relation，（ii）（gs）R（gi＄）. 飴r∀9，・91∈（？，∀86such th為t g梅，98≠の，915≠の． Pefinitien 1．2．14 Let A ：（（？，S） be a ￡raitsformation sernigroup．. Apar嶺1◎難rr：｛猛｝i∈∫on（？i＄called admissible if and ORIy if. there ex三stsゴ∈1S嚢chもhat疏3⊆llゴf・r∀乞d，∀S∈5，・r瓦5＝の． 1）〔壌癖だ。鶏ノ．2．ノ5. Let M ＝（C？，Eli，F） be a state machine， aBd T ＝｛lli｝w an admisslble partltiell on 〈［？． Put M／7r ＝（Y， X，G） and Y ＝＝ 7r． Let ffi，Hj E Y. andσ∈Σ． Define・ifi Gσ＝面戸f and only if瓦・酷⊆・匠ちfor∀i，ゴ∈∫，. ∀σ∈Σ．And puもHiGσ＝のif and only if・伍1も＝の． Then Mノπls called a guetien，t state machine ef rvf with respect te 7r．. P7ηPo5露ゴ。箆f．2．16 Let M ：（｛［？，：，」17） be a state machine． Then IUr／rr ＝：（Y，￡， G） ls a state. machi難e。. Pro（ゾ L蕊Hh＝Hl an dσσ＝＝σア負）r遅鳶フHl∈π，σσ，（穿γ蔓G． Put Hi ww一 ffkG． and ff」’ ww一 HiGT−. Suppese HfojE．＃ e and lliF．＃ ut． Then there exists jllst one eleg｝ent i G f such th ＆t llk F． g Hi ．， and just one elem eRt ］’ E i such th at Hg＝FT g llj． L et ffi fi Hj ＝ ut． ’II］hen. Hg Ca ＝＝ ffj O lill Fa ！ llj，. le.

(17) HkGa ＝ lli 〈〉 Hk Fa K ”i・. Therefore ffi∩Hj≠の，＄o疏＝」匹ノゴ・ Su ppose Hk F．： op or HI F．：￠．. Then疏σ。＝の◎rκβ。：の．. Therefore HkGa ＝ ffgGr ＝ O． U Definition 1．2．f7 Let A ＝（（？，S） be a traitsformation semigroup， and 7r ：｛ffi｝iEi an. admlsslble partitloR on 9． Put Y ＝： 7y． Let Hi，ffj E IY and ＄ E S．. De伽e瓦＊5＝1ちlf鍛d only if瓦5⊆Hj． And de蝕e瓦＊5＝のif and on童yif∫ゐ5 ＝の．. Propositien・！．2． f 8. Let A ＝（｛？，S） be ＆ t・ransformation semigroup． Let i ff 1， and s， s’ E S．. De費ne s∼5／if and◎Rly if Hi＊s；瓦＊5’． Then∼is a c◎ngruence relatlon．. Proof Let s， s’， t G S and s rv s’． As t N t， Hi ＊t ＝： lli ＊t． Let. Hi＊t⊆・ifk． Then（Hi ＊t）＊s g ffk ＊s alld （”i ＊t）＊8’⊆ffk＊5へAs 魚＊s ・ffk＊5’，瓦＊（ts）… Hi＊（彦s’）． Hence・ts∼t＄’． Let s，s’，t E S aBd s nJ s’． Then ffi ＊s ： Hi ＊ s’． Since there exlsts. 丑ゴ∈πsuchもhat lli＊S⊆．Hゴand Hi＊S’⊆正1ゴ， then （Hi ＊s）＊tg H2・＊t ：llk. and （Hi ＊ s’）＊t g Hj ＊t ＝＝ Hk．. As」研＊（sの＝・ffk＝璃＊（5ノリ， st∼s’診． Hence∼is a congrgence re呈＆t董on．目. C脚Uary！．2．ノ9 Let A ＝＝（〈［？，S） be a transformation semigroup． Put S’ ＝： S／ N a＃d 1｝x’ ＝ 7r． Let ffi ff Y， and s E S． Define ”i＊［s］＝： Hi＊s．［1］hen ．4／〈7ir＞：（Y， S’〉 is a traRsformatloR semlroup．. ProPO誘ぎio鍵ノ．2．20 Let M ＝＝（q，Y．um7，，F） be a state machine， and TS（M）＆ transformatlon. semigroup induced by M．［1］hen a partition r on （［？ ls admlsslble with respect eo M， if and only if 7r on Q is admissible with respectte ［｛］S（M）．. ll.

(18) Proof Let a partltion 7； en C？ be admissible with re＄pect to M． Then there ex1sts ］’ G f such that lli，Fl． g Hj for Vi e f， Vff E 2，. ◎r遡源・・の，Since［σ1∈S（M）， then there existsゴ∈isuch th・at lt［g］ g Hj for V i e 1， V［ff］ e S（M）， or ”i［ff］＝＝ e．. Let a partition ＃ on （［？ be admlsslble with respect to TS（M）． Then there exists ／“ G 1 such that ffi［ff］｛ H，・ for Vi G 1， V［a］ E S（！iVf）， or. 瓦［σ］＝の．. Let cr G ￡． ’1”hen there exists s e S（2V） such that ［ff］＝ s． HeRce ￡here exlsts ］’ E i such that HiF． g Uj for Vi E 1， Vff E X， or Hii7．＝：￠．. Proposition i．2．21 Let M ＝（Q，X，，F’） be a state rnachine， and 7r ＝｛Hi｝h・EI an admissible. part・ltion on C？． Then. TS（M／n）：（TS（M））／〈7r＞．. Prαゾ TS（M／rr）＝. （Y， S（M））（Y， S（S（M）））. （TS（M））／〈π〉．. 口. 瑳伽ition！．2．22 Let M ：（Q，X，F） be a state machine， and rr ＝｛M｝iGf an admisslble partition oR q． 1］｝efin．e （｛if”， lx）： 1if 一一一〉！1Ll／7r by ar（g）＝： Hi．， where. 9∈璃，9∈9aRd剛胆， Then（απ，1Σ）is called a桝目編卸襯・励漁 defined by T．. Proposition 1．2．23 Let M ＝（（［？，￡，F） be a state machine． Then （a’r，lx）： M 一〉 M／7； 1s. an eρ三難・rphl＄m．. Proof. Let g E （？，（7 G X aRd gF7．＃￠． Pnt. （απ（の）σ1。（の聯瓦σ・＝葛・. 12.

(19) As rr is admissible， gG． G ff2’． Pllt a7r（glZcr）： Hrk． By the definitioR. of aT， gF． G Hk． As G． and Fi． glve the same uction on g E （？，. 9σ。＝ qFa・Hence罵∩臨≠￠・Si難・eπis a partiもi・n・n Q， Hゴ嵩疏． Hence ar（gFa）＝＝，（avff（g））Gi．（cr）・ Let g．Pi．＝： O． Then clearly ct7r（gF．）！（ctrrr（g））Gi．（．）． As a’“ is surjec−. tive ciearly，（ct7r， 1￡） is a state i：［！achine epimorphism． fi. 1）eノε癬薩。箆ノ，2．24. Leも湾＝（q，s）be a transf・rmati・n semlgr・up， andπ＝｛瓦｝磁an admlssible parti￡ion on Q． Define （fr，gr’）： A 一 A／x by ffr（g）＝： Hi and s”（s）＝： ls］， where q E Hi．， g G （？ and Hi E 7r， s E S．［1］ken （f”，gr）. is called a natural epimorphism defiRed by x．. Proposition f．2．25 Let A＝（Q，S） be a transformatioft semlgroup．［1］hen （frr，gT）： A 一〉 A／n is an epimerphlsm．. Proof Let g E （［？， s G S． P＃t f”（gs）＝ ffk． Since. ！π（9）9’「（5）＝瓦＊［5］＝Hゴ，. similarly to the proof of ProposkloR 2．28， frr（g．） g fT（g）g7T’（，）．. Hence（！π，9つis a transf（）rmation semigroup homom◎rphism、 As∫π and gr are both onto clearly，（fT，g”） is a transfoTmatlo“ semlgroup. epl鵬（｝rphism．口. Proposition ！．2．26 Let M ＝（（［？，X，F） be a state machiRe． Let 7i“ ＝｛ff＆E」 and T’ ＝＝｛K」’｝」’E」 adrnissibie partitions on Q， wheTe T fl｛ 7；” i．e． there exists ］’. @E 」 sucb that Hi （一： 1〈」 for Vi G f． befi ne ct ： ff 一一〉 7；” by a（Hi）＝ Kj．. Then （av，1￡）： 21U／T 一一一〉 M／rr’ is an epimorphism．・. 1）ro（ゾ PuもA4ノπ嵩（y，ΣiG）a難dルf／πノ：（y’，Σ亨σ’）． Let H’i∈yラ ff ff X and lliG． X ￠． Pu￡ a（lliG．）： a（ffk）＝ Ki． Since HiG． g Hk. a・d紘⊆κ1，瓦σ・⊆称P・t（（α（瓦））∼。）瓢Kゴσ・＝κ搬，i・e・， κゴσσ⊆1ぐm・S量鷺ce ffi⊆1ぐゴ， HiGσ⊆・κ臓． Henceκ」∩k’m．≠の， s◎ k’ 堰@＝ li．． Therefore c￥（HiGa）＝（＆（Hi））Gl’．（．）・. 13.

(20) L・田iG・：の・Th…1…lyα（私σσ）・・（・㈹）∼。）・A・α・・d 1Σ are both onto clearly，（cy， 1￡） is a state machlne epimorphism． 1. Tんeo鷲η31，2，27 Let ’ l 一ma （C？，￡， F） and M’ ：（（？’， X’， Fi’） be state machines．. Le￡（ctr，，3）： M 一〉 Mi be an epimorphism． Let x． be an adrr｝isslble. par嶺i◎n de飴ed byα・n A4， andπan admissible partiもi・n・1滅f＄lich thut 7r f 7r．． Then ￡here exists an epimorphism （A， pt）： A4／7r 一 2if’． Furthermere， if ff ＝＝ rr．， then （A， pa） is an lsomorphism．. 1）ro｛ガ Putπ ：｛瓦｝iG∬andπα＝｛．κゴ｝ゴffJ． De伽eλ；π→（∼’by A（ff“ ：｛v（g）， g Ci ffi・. Let瓦，・仏∈πsuch that瓦コ1ノゴ・Asπ≦πα， there exists Is一∼∈πα such that lli C一 Ki． Hence a（g）＝ a（gi） for Vg， gi E ffi． Therefore A is. well−defined． As a is onto， there exists g G q such that a（g）： g’ for Vg’ E （1？’． And slnce there exists Hi G 7r such that g e ffi for Vg G （［？， A is onto．. Define pa ：￡ e X’ by ps ＝ 5． Then ps is clearly well−defilled and onto． Let ”i e x and a G ：． rT heit. （A（ffi））FA（g）＝：（C￥（9））Eb（a） e C？’・. Put HiG．・e Hゴa難d leも9ゴ∈〃ゴ． Then λ（蕉σσ）＝λ嶋）嵩α（％）∈（∼’．. As g E ”i．， gG．＝ g，F． e H，・． Therefore ev（gF．）： cy（g，・）． As （a’．，．5） is an. eplm◎rphlsm，α（9島）⊆（α（9））％（σ）・．Therefbreλ（ffi Gσ）⊆（λ（瓦））Fゑ（の・ Hence （A， ge） is a state rnachine epirr｝orphlsm． Furthermore， consider the case that 7；“ ＝： 7r．． ILet gl，gS G （［？’ such that gl rm一 gS． As a is onto， there exists gi，g2 （ff 〈［2 such that g｛： cy（gi） and. gS ： or（g2）． As gl ＝ gS， a（gi）＝ a（g2）．［1”herefofe there exists H． E T．. such that gi，g2 E ll．． As A ls ento， there exists ”i，ff2 e T such that A（lli）＝ or（gi） and A（H2）＝ a（g2）， where gi E Hi and g2 E H2．. As T ：Ta， Hi ： lla ＝ ff2． TherefoTe A i＄ a one−one mapping． As pa ： 2”1 一￡’ is clearly oRe−oRe，（A， pt） ls a state rr｝achine isomorphism．. Th eo re ？7z ！．2 ．28. Let A ：（｛？，S）＆nd A’ ＝＝（（？’，S’） be trahsforma￡ioR semigrollps． Let. 14.

(21) （ノ，9）・護→A’b・an e繭◎rphism・Letπ∫b・an admissible partiti・n de盒ned by／o難〆隻ラaRdπan admissible partition on〆隻such thatπ≦πノ。 T’hen there exisSs an epimorphism （1，m）： A／〈rr＞一〉 A’．. Furthermore， if r ＝ Tf， then （1， m） is aniserr｝orphism．. 1）roof Putπ・＝｛・研｝薦∫a難dπα＝｛1ぐゴ｝ゴ∈」・Defineど：π→Q’ by l（H∂ ：！（g）， g∈ffi． Byもhe proof of Theorem 2．32，♂is clearly welレde負ned， A鳶ぬs∫is onto，1 is also onto． De簸neμ：5／∼→5／by m（［司）＝9（5∂for s（Ei 5，［8］∈5／∼ラSi∈［5］．．. Let［s玉］，［82］∈S／∼such that圖嵩［＄2］． Then璃＊S、鑑瓦＊S2 f・r. ∀瓦∈π・Asπ≦η， there exlstsノぐゴ∈ηsuch that・仏⊆1ぐゴfbr. ∀瓦臼・Thenκゴ＊5ドκゴ＊82， that is m（［Si］）＝9（51）＝9（82）＝m（［β2］）。. Theぎefbre m is well−defined．．. Let 5ノ∈5ノ． As g：5→5’is◎nも。，もheee exists 5∈5such that g（8）＝＝5へTherefbre there exisもs 3∈5such that m（［5］）＝g（3）・s’． Let・θ『i Gπa難d［3］∈5／∼． Then 1（Hi）禰（［8］）＝：／（9）＊9（＄）. for g∈・lli・Let HiS⊆Hj・a’nd 91∈・窪ゴ・Put 1（M＊［s］）＝♂（ffd＊5）嵩ど（Hj・）ueノ（91）・. As gs∈丑ゴ，／（6s）＝∫（91）． As（∫，9）量s a transf◎rmation semigr◎鞍P e画・rphism，！（gs）⊆∫（9）＊9（s）． Theref・re ど（Hi＊［5］）⊆9（ff∂＊m（［5］）．. Hence（1， m） ls a ￡ransf・rrr｝aも1・ぬsemigr・up epim・rphism．. F慧rthe購◎re， c・n・id・r t穀e ca・e thatπ篇η・Let gl，95∈9’such・that ノノ. 91 ；亨2・. Asどis onto， there exists、ffi，Hk∈x， gl（｛i ffi＆nd g2 G Hk such that. l（H∂＝＝ f（91）＝gl and碑鳶）＝掬2）初灸． As gl；9S，！（gl）＝！（92）． Thereforeもhere existsκゴ∈ηsuch thaも. 9玉，92Cκゴ・Asπ・＝η， Hi ＝．κゴr伍． Theref・re l is a・ite一・ne mal）P圭ng・. Let sl，5灸垂5’such that sl＝sS． As m ls oxt◎， there exists ［51］，［s2］∈S／∼such that m（［Sl］）・9（・1）・・ s1. 15.

(22) and m（［s2］）＝＝ g（s2）：s’，．. A＄9（Sl）＝9（s2）ラ瓦＊s1；・紘＊52 for∀Hi∈π・Asπ＝η，耳ゴ＊Sl…厚ゴ＊ s2 for VH3’ （ 7rf． Therefore ［si］＝［s2］． Hence（1， m） is a transformatlon. semlgr・up isoraorphism．口. 16.

(23) 1．3． Coverings and Products The concept of coverlng ls useful for studies on state ’machiRes and transformatioll semigroups． lt is follnd special｝y effective in studie＄ of ◎fprod魏（二ts．. Definition ！．3．！ Let M＝（（？，￡， F） aftd M’ ：（〈［？’，2’， F’） be state machines．. Let ny ：（［？’ 一〉（？ be a surje￡tive partial fupction and e ：￡一 X’ be a. 鶏＆ppi貰｝g s嚢chもhaち η（9鴇⊆η（9’契（α））. for each g’ G （？’， or E X“，（ny，6） ls a cevering of 2U by t｝4’， written lif 〈，Vi．. Pefinitien f．3．2 Let A ＝（（［？，S） and B de （］P，［Z”） be transformation semigroups．. Le切：P→Qbe a surjecもlve partlal f鷺瞭1◎鍛． Assume there exists ts e T for V＄ E S such that. n（p）一s ｛ll n（p・t，）. for each p E P．［1］hen we call B cover＄．4， wrltten A g B． ep ls called a. covering ef A by B． And t， e T ls called a eovering element fer s E S．. Lemma i．3．3 Let A ＝（q，S） and B ＝（，i？， T） be transformation semigrollps．. And other conditiens are the same as Definltion 1．3．2． Assume there exlsts t， G T for Vs e S such that. n（p）一 s g ep（p ・ t，）. fer each p E ，1’． And assume there exlsts t，i e T for V＄’ E S such that. n（p）・ s’ g n（p ・ t，s）. for each p G ，F）． rlihen thete exists t，・ t，s E T for Vss’ G S such that. ny（p）・ss’ ｛1 ny（p・tS・t，，）. for each p G P．. 17.

(24) Proof. Let s， sS E S and p G uP．［1］hen. 77（pa）ss’. ＝（？7 （P） s） st. ｛21 n（pt．）s｛・. ｛g： ny（1）tstsi）．. n iF’roposition ！．3．4 （［4］）. Let （（？i，， Si） be transfermatioR serr｝igroups for i ww一 1，2，3， where （（？i，Si） S （（？2， S2） and （（？2， S2） f｛（（？3， S3）． TheR. （Qi，Si） S （e3， S3）・. Proof Let （（？i，SD f｛（（［？2，S2）．［E］heR there exists a surjective partial function epi ：（［？・2 一〉（［？i， and a t，，（1 S2 for Vsi （ff Si， Vq2 G （［？2. such that M（92）Si ｛1： ni（g2ts，）・. Let （（［？2， S2） S （q3， S3）．［1”hen there exists a surjective partial func￡lon be ：（［？3 一一一〉 Q2， and a ts， E S3 for Vt＄， E S2， Vg3 E Q3 slich that. η2（93）診51⊆η2（93ち2）．. Define n3：（？3 一一〉 C？i by. ny3（g3）＝ nyi（ep2（g3））. fbr g3∈（∼3． C董ear玉yη3 is a surjecも三ve partial f疑鞭。もlon．. Let si E Si aRd g3 E 93． Then there exists a t，， G S3 such that. ep3（93）Si ：＃i（M（93））Si st m（n2（g3）ts，） g ni（ep2（g3 t，，））. ＝ n3（g3t，，）．. Thlls （（［？i，SD S （〈？3， S3）＃ O. 18.

(25) Theorem 1．3，0’” Let M・＝＝（Q，Σ，、F） and A｛f”＝＝（（？s，ΣノラF’） be state machines such thaも. M〈 M’． Then TS（M） S tS（，Ntti）．. P・reof Slltce M ：s； 21Vf’， there exist a surjective partial fuRctlon n ： q’ 一 q and a function C ：￡一一〉￡’ such that. η（9’罵⊆η（9’屡（。））. for Vg’ G C？’ and Va E X’．. Put TS（A・1）＝（（∼，S（ルf））＝（Q，3）a灘d ’llr’s（．M’）＝（Q’，S（M’））＝（（［？’，S’）． Let s ff S． Then there exlsts a G ￡＊ such that s ：［a］． Put t，＝ 16（a）］ E S’． ’1］hen. n（6’）s ＝＝ ny（g’）F．. ⊆η（9ノ契（α））. ・・η（4勾. for Vg’ E （1？’． Therefere there exists t． E S’ such that. n（g’）s g n（g’t．）. for Vs G S and Vg’ E （？’． Hence ［1］S（Atl） E｛ TS（l14’）． E］. Definitie n 1 ． ge． 5. Let M＝（（？，：， F） and M’ ＝＝（e’，￡’，17’） be complete state machines．. （1） Define thelr restricted direct product ：. MA Mt ：（q × （［？’，￡， FA ，1 ”），. in the special case where ￡＝ Y−7’ only， by. （，F A F’）（（g， g’）， ff）＝（17（g， ff）， F’（d， ff））. for a e ￡，（g， q’） G （？ × C？’．. （2） Define the （fttll） direct product of A4 and A，1’， M × M’ ＝（（？ × Q’，X x ￡’，F × Fi） where. （F × F’）（（g， g’），（q d））＝＝（F（g， g）， F’（g’， a’））. 19.

(26) for ff G ：， e’ E Y．r，’，（q， g’） E ｛2？ × （？’．. （3） Define the cascade product ef M and M’ with respect to w ：（？’ × ：’ 一一一〉￡ by. A4『ω沸fノ＝（Q×（∼ノ，Σ’，Fω）. where FW（（g， g’）， a’）＝＝（，1？（g，w（g’， a’））， F’（g’， g’）），. for ff’ G ￡’，（g， g’） G （？ × C？’．. （4） Define the wreath product， M o A・f’， of M and ！114’ where MoMi ．，（（［？ × （？i， v．，Q’ × x，， f70）. afid F。（（g， g’），（∫，め）＝（F（9， f（の），F’（4，の） for ff’ （i 2’，f （i 2］‘？’，（g，g’）（1 q × q’・. Propesition・ 1．S．7 Let M ＝（C？， E］，． F） aBd M’ ＝（Q’，￡，，，IF，t） be state machines． Let ee E X＋. ［α］〈〔≡S（・W〈ふ4s），［α】∈S（．M）and［α］’∈S（ルW’）。 Then ［α］。＝回∩［α］’。. ．1’roof Let 5 G ￡＋ sllch that ，8 E ［or］A． Then （F A 17’）（（g， 4），，S）＝：（F A F’）（（g， d）， a）. 拓r殉4）ε（∼×Q’．. O. （9塩9’％）＝（9凡，4鳳） for Vq e q and V4 G q’．. o gllB ：g」P7a for Vq e Q，， aRd. 4％算9’鳳 for Vd E c？t．. o. ［a］A ｛ll ［cv］ fi ［cv］’. 2g.