順序機械の同調性と変換半群に関する考察

(1)

順序機械の同調性と変換半群に関する考察

清木泰 ^弌＊

A Consideration on the Synchronization of Sequential Machines and the Transformation Semigroups．

by

Yasukazu SEIKI

（Electrical Engineering）

Following the previous report， this paper discusses the synchronization of sequential machines on the transformation semigroups which correspond to machines．

It is shown that a general condition for the synchronization of rnachines is given on the transformation semigroups containing constant transformations．

Unfortunately， however， this condition tells about nothing how to construct・a constant trans・

formation or a synchronizing sequence．

Concerning with this point， the 璽哩range and the 配電partition related to the structure of a transformation allow us to give a general condition for the construction of a constant transfor・・

mation by a combination of any transformations．

1．まえがき

本報告は，前報告1）に引き続き順序機械の同調性を論じたものである．前報告では，同調性そのものの定義づけや，状態集合にある制限（主としてSP分割）

を加えた場合の考察がなされた．その結果，SP状態分割をもつ機械だけに対して同調性の条件が得られたが，さらに一般的な機械の同調性に関する考察を行うまでには至らなかった．

順序機械の代数的構造に関するいくつかの研究が，

主としてその半群構造に関連して報告されているが，

本稿においては，順序機械をその変換半群上で論ずることにより，同調性の問題を考察した．同調系列1）は変換半群における定値変換に対応するので，機械の同調性に関する問題は定値変換を含む変換半群の問題に帰着されることがわかる．このような変換半群上での順序機械の考察により，前報告の課題であった機械の同調性に関する一般的な条件が，きわめて単純な命題

として与えられることがわかった．

しかしながら，同調系列に相当する定値変換そのものの構成に関しては，この命題は何も与えていない．

＊電気工学教室

この点に関して，変換に関した値域（range）と同値分割（partition）という二つの概念が，定値変換構成のためのきわめて重要な条件を与える．なお，前報告では，変換の値域のみに関して機械の同調性が論じられていたことがわかる．さらに，値域と同値分割を用いた同調系列（すなわち定値変換）の求め方の具体例を示し，同調グラフ2）を用いた方法との比較検討も行

なった．

以上が本報告の内容である．前報告においては機械の状態集合が主な考察の対象であったのに対し，本報告においては状態集合上での写像すなわち変換および変換そのものの構造等が考察の対象となっている．

2．変換半群と順序機械

順序機械と半群との結びつきは，状態集合における

写像（もしくは変換）の集合として表現された順序機

械の代数的構造に起因する．すなわち，順序機械にお

ける入力および入力系列は状態集合における写像であ

り，この写像の集合は写像合成の演算に関して結合性

と閉包性を有するから半群を形成する．（この点に関

してはすでに証明されているので，ここではその詳細

には立ち入らないことにする。）このような半群を機

(2)

械に付随した入力半群という．入力半群に関連して，

本稿では順序機械の動きを変換半群上で表現することにより，その同調性に関する考察を行なうことにする．

以下に，変換半群に関する定義を順序機械の動きと対応させながら与えていく．なお，順序機械のモデルとして，前報告と同様，出力を除いたMoore形機械を

考える．

オ＝＜S，Σ㌔M＞

ここに，Sは内部状態の集合，，Σ＋は入力半群，そしてMは次のような状態遷移写像を表わす．

M：S×Σ＋→S

（定義2．1）集合S上の変換αを次のように定め

る．

S＝｛s1， s 2，…， sn｝に対して

α一（SI S2 SnS1／ S2ノ・。・Snノ）

あるいは単にα＝（S11， S2 …， S。）と表わす．

ここに，SiノεSα＝・1，…， n）であり， Sの勲章に対してσ．との演算を次のように定める．

Si・α＝＝Si 1（＝1，…， n）

また，順序機械Aにおいてαに対応した入力系列α が存在するとき，明らかに

Si・α・＝Siノ←→M（Si，αノ）鵠Siノ

となる．以後，変換αに対応した入力をαで表わすとき，変換の性質が順序機械において表わされるもの

とする．

9（定義2．2） Ts〔A〕を機械A＝〈S，Σ＋，M＞

の変換半群という．ここに；哩Σ＋は入力半群を表わす．

Ts〔A〕にはこの入力半群の任意の元と対応する変換が存在する．すなわちTs〔A〕の元αとΣ＋の元α1との間に，定義2．1で述べた関係が成立するものとす

る．

このような機械に対応した変換半群の構成により，

機械の動きを変換という演算を用いて表わすことができる．次の定義は同調系列に対応するものである．

（定義2，3）S＝｛s1，s2，…， S・｝とするとき，

S上の変換（s1ノ， s2ノ，…， s・、ノ）においてs1ノ＝s2ノ

＝…＝S・、ノ（＝Si）であるような変換を定値変換とい

い，θ量で表わす．

明らかに次の関係が成立する．

（i）VsεS， sθi＝si←→M（s，θノi）＝s量

（ii） VαεTs〔A〕，α・θi＝・θi

（VsεS， M（s，αノθノi）＝M（M（s，αノ），θノi）

＝Si∴α・θi＝Oi）

（iii）Si●α＝Sj なるαに対して

θi・α＝θ」

（VsεS， M（sθ」ノαノ）＝M（M（s，θノi），αノ）

＝M（Si，αノ）＝Sj ∴ θi・α＝θj）

以上の定義により，前報告の課題であった順序機械の同調性に関する一般的な条件は，次のような単純な命題として与えられることがわかる．

〔定理2．4〕機械Aが同調（完全同調）するための必要十分条件は，その変換半群Ts〔A〕が定値変換を含むことである．

（証明）（必要なこと）機械が完全同調して，次のような同調系列1＊をもっと仮定する．

VsεS， M（s，1＊）＝s＊

1＊は入力記号の集合Σの元の系列であり，かつ機械Aの動きに順じて定められるものであるから，入力半群Σ＋に含まれることは明らかである．1＊＝θ1とすれば，θ に対応した変換θがT，〔A〕中に存在しかつ次の関係を満たすことも明らかである．

VsεS， s・θ＝s＊←→M（s，θ1）＝s＊

したがって，θは定値変換である．

（十分なこと）上記の如きθが T、〔A〕において存在すると仮定する．変換半群の結合性と閉包性から，

最：終的には，θはΣの元に対応した変換だけの結合として表わすことができる．これが入力系列1＊すなわち同調系列に対応したものになることは明らかである．（QED）

上記の定理は，同調系列とそれに対応した定値変換の存在の証明により，機械の同調性に関する一般的な条件を与えたものであるが，定値変換自体の一画的な構成に関しては何も明らかにされていない．この点については次節で詳しく論ずることにする．

以上の議論から，機械の同調性に関する問題は，定値変換を含む変換半群の問題に帰着されることがわか

る．この問題に対する考察を深めるためには，半群の本質的な構造に関する知識が要求される．

3。値域と同値分割による定値変換の構成定理2．4は機械の同調性に関する一般的な条件を与えるものであったが，定値変換自体の構成に関しては何も明らかにされなかった．そこで，本節においては，変換回忌の一つの特徴づけであるrange （これを値域とよぶことにする）とpartition（これを同値分割とよぶことにする）の概念を用いて，定値変換構成のための一般的な条件を与える．

まず，値域と同値分割に関する定義を示す．

（定義3．1）3）集合S上の変換αに対して，

S・αをαの値域という．明らかに，

S・αqs÷『→M（S，αノ）⊂lS

である．

(3)

順序機械の同調性と変換半群に関する考察

（定義3．2）3）集合S上の変換αに対して，

Pα＝αoα一1

（si，sjεS． si Pαsj←→si・α＝sj・α）

なるPαを定義する．明らかにPαはS上の同値関係を表わす．このとき，

Pα（S）＝＝｛Eα（ユ），Eα（2），…， Eα（「）｝

を，変換αによるSの同値分割（あるいは単に変換 αの同値分割）という．ここに，

UEα（i）＝・S＆Eα（i）nEα（」）＝A（i≠」）

i＝1

＆Eα（i）・α＝s（i）←→M（Eα（り，α！）＝s（i）

である．したがって，各Eα（Dはα（すなわちPα）

による同値類を表わしている．

上記の定義から次の関係が得られる．

〔定理3．3〕3）lS・αi＝IPα（S）1．

（証明） S・α←→M（S，αノ）

＝M（Eα（1）Eα（2）…Eα（「），αノ）

＝｛M（Eα（1），αノ），M（Eα（2），αノ），…，

M（Eα（r），αノ）｝＝｛s（1），s（2），…， s（r）｝，

Si ≠Sj （i≠j）

すなわち，αの値域における元の数とPαによる同値類の数は，上式の場合いずれもrであるから，等しくなることがわかる．（QED）

（定義3．4）3）IS・α1＝lPα（S）1＝r とするとき，rをαのrank（階数）という．

以上の定義から，変換半群において定値変換を求めることは，階数が1である変換を求めることに他ならないことがわかる．なお前報告においては，値域のみに関して階数が1となるような変換を求めることが，

変換構成の主題であったといえる．これに対して，本稿においては，値域と同値分割の相互関係により，主として同値分割に関して階数が1となるような変換構成を目的としている．

次に，定値変換構成に先立ち，変換の同値分割に関する基本的な関係を論ずる．変換半群において，任意の二つの変換α，βを結合させて一つの変換γ＝α・β を構成したとき，αの同値分割とγの同値分割との問には次のような包含関係が成立する．

〔定理3．5〕変換αの同値分割をPα（S），変換γ＝α・β（βは任意）の同意分割をPγ（S）とするとき，常に次式が成立する．

Pα（S）≦Pγ （S）

（証明） Eα（i），Eα（i＋1），…， Eα（i＋「一1）εPα（S）

なるr個の異なる同値およびβの同値類

Eβ（k）εPβ（S）（＆M（Eβ（k）・βノ）一・（kり

考える．これらの問に次の関係が成立すると仮定する．

M（E・（）E宴＋1）…E・（＋「r1）・α1）dEβ（k）

このとき、γ・＝α・βに対して

M（Eα（i）Eα（i＋1）…Eα（i＋卜1），α β ）＝M（M（Eα（i）Eα（i＋1）…Eα（i＋「一1），αノ），βノ）

qM（Eβ（k）・βノ）＝s（k）

となる．したがって，Eα（i）Eα（i＋D…Eα（i＋「一1）は変換

γ＝α・βに対して一つの同値類を形成することになる．一・方，上記の如きβの同値類が存在しない場合，

Pα（S）における任意の二つの同値類Eα（DとEα（」）

に対して，

M（Eα（i）Eα（」），αノβ！）＝M（M（Eα（i）Eα（」），

α！）・β ）竃M（s（i）s（j）・βノ）δPβ（S）・

S（i）≠S（j）

（εはεの否定を表わすものとする）●

したがって，S（i）， S（」）ゴは各々βにより常に相異なる値をとるから，同値類E話i 〉，Eα（」）が同じ一つの同値類となることは起らない．また，最初与え

られた変換の同値分割が他の変換との結合によって分解しないことも明らかである．このとき定理の等号が

成立する，

以上の結果を総合して，定理の成立が証明される．

（QED）

このように，いくつかの同値類が結合して一つの同値類となることを，同値分割の拡大ということにする．

上記の定理は，同値分割の拡大が定値変換構成の二つの手がかりであることを示している．事実，任意の二つの変換の結合により定値変形を構成する場合，前者変換の同値分割を後者変換の同値分割により，一度に一つの同値類をもつ同値分割に拡大することが行われ

る．そのための条件として次の定理が与えられる．

〔定理3．6〕任意の二つの変換α，βに対して α・β＝θ（定値変換）

となるための必要十分条件は，αの値域S・αとβ の同値分割Pβ（S）との間に，次の関係が成立するこ

とである．

ヨEβ（k）εPβ（S）・S・αdEβ（k），

（証明）（必要なこと）

S・αβ＝S・θ＝s（k）

とする．S・αqsであるから，

M（S・α，βノ）qM（S，βノ）

＝（Eβ（1）Eβ（2）…Eβ（k）…Eβ（「）・β ），＆

M（S・α，βノ）＝M（S，αノβノ）ニM（S，θ！）＝s（k）

したがって，上式はPβ（S）において

MIEβ（k）・β1）＝s（k）

(4)

となるようなEβ（k）が存在することを示している．

∴ M（S・α，βノ）＝M（Eβ（k），β ）＝s（k）

一一s・α一Eβ（k）

次に， SαdEβ（◎を証明しよう．

S・α⇒Eβ（≧）（S・α≠Eβ（k））と仮定するる．このとき次式が得られる．

M（S・α，β ）；⊃M（Eβ（k），βノ）二s（k）

仮定により，S・αは次のように分解できる．

S・α＝Eβ（k U（S・α＼Eβ㈲）

（ここに，＼は集合の差を表わす）．

．●．M（S・α，βノ）（＝s（k））

一M（Eβ（k ・βノ）UM（S・α＼Eβ（k），β ）＝s（k）UM（S・α＼Eβ（k）・β ）・

S・α≠Eβ（k）であるから，上式の第二項はある値をもつ．したがって，s（k）がs（k）と空でない値の和として表わされることになり，これは明らかに矛盾

する．

∴s・α口Eβ（k）

（十分なこと） S・αdEβ（k）であるからβによる両辺の値を求めれば，

M（S・α，βノ）qM（Eβ（k）・β ）＝s（k）

であるから，明らかに

M（S・α，βノ）＝・M（S，αノβ1）＝s（k）

が成立し，定値変換の定義から α・β＝θ

であることがいえる．（QED）

このように前老変換の値域と後者変換の同値分割との包含関係により，定値変換構成のための条件が与えられることが明らかにされた．一般に，複数個の変換の結合として定値変換が与えられている場合，変換の結合性により，これを任意に二分割して二つの変換の結合として表わすごとができるから，次のような命題が定理3．6の系として与えられる．

〔系3．7〕変換の系列α1，α2，…，αmに対して，

これらの結合α1α2…αmが定値変換となるための必要十分条件は，その任意の二分割αニα1…αk，

β＝αk＋1…αmが定理3．6を満たすことである．

（証明）ほとんど自明であるので省略．

以上の結果から，機械に対する変換半群における定値変換は，入力記号に対応した変換の結合として表わされるから，同調系列を求めるための条件として，変換の値域と同値分割に関する上記の定理が適用できる

ことは明らかである．

4．変換の値域と同値分割を用いた同調系列の求め方前節で定値変換構成のため一般的な条件が与えられたから，本節においてそれを用いた同調系列の求め方の具体例を示し，あわせて前報告で用いた同調グラフ2）による方法との比較検討を行なう．

Fig．1のような状態遷移表をもつ順序機械について考察してみよう．この状態遷移表からただちに，各入力に対する変換の同値分割が次のように与えられる

ことカミ：わかる．

Fig．1 State transition table．

0 1

1

2 3 4

Po（S）ゴ｛（14）， 2， 3｝

P1（S）＝｛（13）， 2， 4｝

これらの同値分割の各同値類に状態を割り当てる写像をそれぞれ伽，ρ1とし，次のように表わす．

伽｛（1）三1・伽｛（1）二i・

なお，ρα（S）＝S・αとなることは明らかである．

また，甲xy二二yOρxである．

上の例では，同値分割拡大のためには

亨）x（Sノ） d （14） or （13）， S d S

となるようなxおよびS を求めることが必要である．

いま，S1＝｛（14），2｝とすれば， x＝0すなわち90 により

亨）o（S！）＝｛3， 1｝＝（13）

となることカミわかる．（13）は甲1により2となるから，入力系列01によりSノは2なる値をもつ一つの同値類となる．したがって

伽｛愕）圭（134）±1

となる．ここで，ρ01に対する値域は

〜Oo1 （S）＝（12） q （124）

であるから，再び伽1を用いて

〜ρ01 〔〜ρ01 （S）〕＝ρ010〜oo1 （12）＝2

となることがわかる．したがって，入力系列0101は

同調系列となり，このとき機械は状態2に同調するこ

とがわかる．この他にも同調系列は存在するが，上記

(5)

順序機械の同調性と変換半群に関する考察

と同様の方法で求められるので省略する．

同じ機械に対する同調系列を，同調グラフを用いて求めてみよう．Fig．2にその同調グラフを示す．図中，太実線および太破線はそれぞれ同調状態に至るまでの最短入力経路を表わす．この図から先に求めた同調系列0101が最短のものであることがわかる．

（1234）

（134）一＿L（1

／：＼1

（34）一一（12）一

9＼・↓＼

（13）

↓1

（2）来

2塵

11

▼

（2 3）・

1 13

10

（14）

醤屡 0 曹

（3）来 Fig．2 Synchroniz！ng graph．

このように同調グラフフによる方法は，最短の同調系列を求める場合には有効であるが，状態の数の増加に伴い図の複雑さが増すので，あまり実用的ではない．

また，この同調グラフでは，同値分割に関する情報は全く用いられていない．

一方，本稿で述べた方法は，最短の同調系列を与え

るという保証こそないが，値域と同値分割に関する情報を同値分割拡大において有効に用いることにより，

比較的単純な操作のくり返しにより同調系列が得られるという点で，一般の順序機械の同調性を調べるのに適した方法であるといえる．

5．あとがき

機械の同調性を変換半群において論ずることにより，

同調性に関する一般的な条件が，定値変換を含む変換半群上で与えられた．さらに，変換自体の構造を値域と同値分割で特徴づけることにより，定値変換構成のための重要な関係が得られた．

筆者の最初の目的は，与えられた順序機械の入力に対応した変換の値域と同値分割に関する情報のみを用いて，機械の同調性に対する判別条件のようなものを求めることであったが，本稿ではその点に関して満足な結論は得られなかった．これと関連して逆に，機械の非同調性に関する条件を求めることも重要な問題であると思われる．以上，残された新たな課題については，機会を改めて検討したいと考えている．

順序機械の同調性と変換半群に関する考察

順序機械の同調性と変換半群に関する考察

A Consideration on the Synchronization of Sequential Machines and the Transformation Semigroups．

by

Yasukazu SEIKI

（Electrical Engineering）

Following the previous report， this paper discusses the synchronization of sequential machines on the transformation semigroups which correspond to machines．

It is shown that a general condition for the synchronization of rnachines is given on the transformation semigroups containing constant transformations．

Unfortunately， however， this condition tells about nothing how to construct・a constant trans・

formation or a synchronizing sequence．

Concerning with this point， the 璽哩range and the 配電partition related to the structure of a transformation allow us to give a general condition for the construction of a constant transfor・・

mation by a combination of any transformations．

1．まえがき

本報告は，前報告1）に引き続き順序機械の同調性を 論じたものである．前報告では，同調性そのものの定 義づけや，状態集合にある制限（主としてSP分割）

を加えた場合の考察がなされた．その結果，SP状態 分割をもつ機械だけに対して同調性の条件が得られた が，さらに一般的な機械の同調性に関する考察を行う までには至らなかった．

順序機械の代数的構造に関するいくつかの研究が，

主としてその半群構造に関連して報告されているが，

として与えられることがわかった．

しかしながら，同調系列に相当する定値変換そのも のの構成に関しては，この命題は何も与えていない．

＊電気工学教室

以上が本報告の内容である．前報告においては機械 の状態集合が主な考察の対象であったのに対し，本報 告においては状態集合上での写像すなわち変換および 変換そのものの構造等が考察の対象となっている．

2．変換半群と順序機械

順序機械と半群との結びつきは，状態集合における

写像（もしくは変換）の集合として表現された順序機

械の代数的構造に起因する．すなわち，順序機械にお

ける入力および入力系列は状態集合における写像であ

り，この写像の集合は写像合成の演算に関して結合性

と閉包性を有するから半群を形成する．（この点に関

してはすでに証明されているので，ここではその詳細

には立ち入らないことにする。）このような半群を機

械に付随した入力半群という．入力半群に関連して，

本稿では順序機械の動きを変換半群上で表現すること により，その同調性に関する考察を行なうことにする．

以下に，変換半群に関する定義を順序機械の動きと対 応させながら与えていく．なお，順序機械のモデルと して，前報告と同様，出力を除いたMoore形機械を

ここに，Sは内部状態の集合，，Σ＋は入力半群，そ してMは次のような状態遷移写像を表わす．

（定義2．1） 集合S上の変換αを次のように定め

ここに，SiノεSα＝・1，…， n）であり， Sの勲章 に対してσ．との演算を次のように定める．

また，順序機械Aにおいてαに対応した入力系列α が存在するとき，明らかに

Si・α・＝Siノ←→M（Si，αノ）鵠Siノ

となる．以後，変換αに対応した入力をαで表わす とき，変換の性質が順序機械において表わされるもの

9（定義2．2） Ts〔A〕を機械A＝〈S，Σ＋，M＞

の変換半群という．ここに；哩Σ＋は入力半群を表わす．

Ts〔A〕にはこの入力半群の任意の元と対応する変換が 存在する．すなわちTs〔A〕の元αとΣ＋の元α1と の間に，定義2．1で述べた関係が成立するものとす

このような機械に対応した変換半群の構成により，

機械の動きを変換という演算を用いて表わすことがで きる．次の定義は同調系列に対応するものである．

（定義2，3）S＝｛s1，s2，…， S・｝とするとき，

＝…＝S・、ノ（＝Si）であるような変換を定値変換とい

明らかに次の関係が成立する．

（i）VsεS， sθi＝si←→M（s，θノi）＝s量

＝Si∴α・θi＝Oi）

（iii）Si●α＝Sj なるαに対して

＝M（Si，αノ）＝Sj ∴ θi・α＝θj）

以上の定義により，前報告の課題であった 順序機 械の同調性に関する一般的な条件 は，次のような単 純な命題として与えられることがわかる．

〔定理2．4〕 機械Aが同調（完全同調）するため の必要十分条件は，その変換半群Ts〔A〕が定値変換 を含むことである．

（証明） （必要なこと）機械が完全同調して，次の ような同調系列1＊をもっと仮定する．

VsεS， s・θ＝s＊←→M（s，θ1）＝s＊

したがって，θは定値変換である．

（十分なこと）上記の如きθが T、〔A〕において存 在すると仮定する．変換半群の結合性と閉包性から，

最：終的には，θはΣの元に対応した変換だけの結 合として表わすことができる．これが入力系列1＊す なわち同調系列に対応したものになることは明らかで ある． （QED）

以上の議論から，機械の同調性に関する問題は，定 値変換を含む変換半群の問題に帰着されることがわか

る．この問題に対する考察を深めるためには，半群の 本質的な構造に関する知識が要求される．

まず，値域と同値分割に関する定義を示す．

（定義3．1）3） 集合S上の変換αに対して，

S・αをαの値域という．明らかに，

S・αqs÷『→M（S，αノ）⊂lS

順序機械の同調性と変換半群に関する考察

（定義3．2）3） 集合S上の変換αに対して，

Pα＝αoα一1

（si，sjεS． si Pαsj←→si・α＝sj・α）

なるPαを定義する．明らかにPαはS上の同値関 係を表わす．このとき，

を，変換αによるSの同値分割（あるいは単に変換 αの同値分割）という．ここに，

である．したがって，各Eα（Dはα（すなわちPα）

による同値類を表わしている．

上記の定義から次の関係が得られる．

〔定理3．3〕3）lS・αi＝IPα（S）1．

（証明） S・α←→M（S，αノ）

すなわち，αの値域における元の数とPαによる同 値類の数は，上式の場合いずれもrであるから，等し くなることがわかる． （QED）

（定義3．4）3）IS・α1＝lPα（S）1＝r とするとき，rをαのrank（階数）という．

以上の定義から，変換半群において定値変換を求め ることは，階数が1である変換を求めることに他なら ないことがわかる．なお前報告においては，値域のみ に関して階数が1となるような変換を求めることが，

変換構成の主題であったといえる．これに対して，本 稿においては，値域と同値分割の相互関係により，主 として同値分割に関して階数が1となるような変換構 成を目的としている．

〔定理3．5〕 変換αの同値分割をPα（S），変 換γ＝α・β（βは任意）の同意分割をPγ（S）とす るとき，常に次式が成立する．

本報告は，前報告1）に引き続き順序機械の同調性を論じたものである．前報告では，同調性そのものの定義づけや，状態集合にある制限（主としてSP分割）

を加えた場合の考察がなされた．その結果，SP状態分割をもつ機械だけに対して同調性の条件が得られたが，さらに一般的な機械の同調性に関する考察を行うまでには至らなかった．

しかしながら，同調系列に相当する定値変換そのものの構成に関しては，この命題は何も与えていない．

以上が本報告の内容である．前報告においては機械の状態集合が主な考察の対象であったのに対し，本報告においては状態集合上での写像すなわち変換および変換そのものの構造等が考察の対象となっている．

本稿では順序機械の動きを変換半群上で表現することにより，その同調性に関する考察を行なうことにする．

以下に，変換半群に関する定義を順序機械の動きと対応させながら与えていく．なお，順序機械のモデルとして，前報告と同様，出力を除いたMoore形機械を

ここに，Sは内部状態の集合，，Σ＋は入力半群，そしてMは次のような状態遷移写像を表わす．

（定義2．1）集合S上の変換αを次のように定め

ここに，SiノεSα＝・1，…， n）であり， Sの勲章に対してσ．との演算を次のように定める．

となる．以後，変換αに対応した入力をαで表わすとき，変換の性質が順序機械において表わされるもの

Ts〔A〕にはこの入力半群の任意の元と対応する変換が存在する．すなわちTs〔A〕の元αとΣ＋の元α1との間に，定義2．1で述べた関係が成立するものとす

機械の動きを変換という演算を用いて表わすことができる．次の定義は同調系列に対応するものである．

以上の定義により，前報告の課題であった順序機械の同調性に関する一般的な条件は，次のような単純な命題として与えられることがわかる．

〔定理2．4〕機械Aが同調（完全同調）するための必要十分条件は，その変換半群Ts〔A〕が定値変換を含むことである．

（証明）（必要なこと）機械が完全同調して，次のような同調系列1＊をもっと仮定する．

（十分なこと）上記の如きθが T、〔A〕において存在すると仮定する．変換半群の結合性と閉包性から，

最：終的には，θはΣの元に対応した変換だけの結合として表わすことができる．これが入力系列1＊すなわち同調系列に対応したものになることは明らかである．（QED）

以上の議論から，機械の同調性に関する問題は，定値変換を含む変換半群の問題に帰着されることがわか

る．この問題に対する考察を深めるためには，半群の本質的な構造に関する知識が要求される．

（定義3．1）3）集合S上の変換αに対して，

（定義3．2）3）集合S上の変換αに対して，

なるPαを定義する．明らかにPαはS上の同値関係を表わす．このとき，

すなわち，αの値域における元の数とPαによる同値類の数は，上式の場合いずれもrであるから，等しくなることがわかる．（QED）

以上の定義から，変換半群において定値変換を求めることは，階数が1である変換を求めることに他ならないことがわかる．なお前報告においては，値域のみに関して階数が1となるような変換を求めることが，

変換構成の主題であったといえる．これに対して，本稿においては，値域と同値分割の相互関係により，主として同値分割に関して階数が1となるような変換構成を目的としている．

〔定理3．5〕変換αの同値分割をPα（S），変換γ＝α・β（βは任意）の同意分割をPγ（S）とするとき，常に次式が成立する．

γ＝α・βに対して一つの同値類を形成することになる．一・方，上記の如きβの同値類が存在しない場合，

したがって，S（i）， S（」）ゴは各々βにより常に相異なる値をとるから，同値類E話i 〉，Eα（」）が同じ一つの同値類となることは起らない．また，最初与え

られた変換の同値分割が他の変換との結合によって分解しないことも明らかである．このとき定理の等号が

このように，いくつかの同値類が結合して一つの同値類となることを，同値分割の拡大ということにする．

〔定理3．6〕任意の二つの変換α，βに対して α・β＝θ（定値変換）

S・α⇒Eβ（≧）（S・α≠Eβ（k））と仮定するる．このとき次式が得られる．

一M（Eβ（k ・βノ）UM（S・α＼Eβ（k），β ）＝s（k）UM（S・α＼Eβ（k）・β ）・

S・α≠Eβ（k）であるから，上式の第二項はある値をもつ．したがって，s（k）がs（k）と空でない値の和として表わされることになり，これは明らかに矛盾

（十分なこと） S・αdEβ（k）であるからβによる両辺の値を求めれば，

であることがいえる．（QED）

これらの結合α1α2…αmが定値変換となるための必要十分条件は，その任意の二分割αニα1…αk，

（証明）ほとんど自明であるので省略．

以上の結果から，機械に対する変換半群における定値変換は，入力記号に対応した変換の結合として表わされるから，同調系列を求めるための条件として，変換の値域と同値分割に関する上記の定理が適用できる

Fig．1のような状態遷移表をもつ順序機械について考察してみよう．この状態遷移表からただちに，各入力に対する変換の同値分割が次のように与えられる

これらの同値分割の各同値類に状態を割り当てる写像をそれぞれ伽，ρ1とし，次のように表わす．

となることカミわかる．（13）は甲1により2となるから，入力系列01によりSノは2なる値をもつ一つの同値類となる．したがって