Microsoft Word ã‡»ã…«ã‡ªã…¼ã…‹ã…žã…‹ã…³ã†¨åłºæœ›å•¤(佒芤喋çfl�)

Transcription

1 Cellulr uo nd heir eigenlues 東洋大学総合情報学部 佐藤忠一 Tdzu So Depren o Inorion Siene nd rs Toyo Uniersiy. まえがき 一次元セルオ-トマトンは数学的には記号列上の行列の固有値問題である 固有値問題の行列はふつう複素数体上の行列である 量子力学における固有値問題も無限次元ではあるが関数環上の行列でその成分は可換環である しかし セルオートマトンは非可換環上の行列の固有値問題である セルオートマトンの対象は記号列で乗法は連接である 連接は最も自然な非可換演算である 複素数体上の行列を非可換環上の行列に広げるにはいろいろあるが記号列上の固有値問題は複素数体上の固有値問題の自然な拡張になっている セルオートマトンはその振る舞いをあらわす並列写像の性質によって単射 定数対 写像 全射 非全射のつに大きく分類される 本論文では各クラスの固有値 固有ベクトルについて論じる. 諸定義 一次元セルオ - トマトン C とは C Z Q N の四組で与えられる ここで Z は整数の集合で各オ - トマトンが配置されている位置の集合表わす Q は各オ - ト マトンの状態を表す記号列の有限集合 N は Z の有限部分集合で近傍と呼ばれる 局所関数 : Q N Q は Q } N = n のとき 状態 スコープ幅 n の { 局所関数という : Z Q なる写像 を様相といい 各オ-トマトンの状態の分布を表わす この様相に局所関数 で一斉に変換すると新しい様相 ' は ' i i i i N or ll i Z で与えられる ' なる対応を ' と書く C で様相の集合を表すとシフト写像 : C C は i i で定義される Z に対して 写像 : C C を並列写像という - -

2 wq Q の元の連接を乗法とすると Q は単位元 null word をもつモノイドである * に対して w はワードの長さを表す C を複素数体とする C の元の長さは である wq に対して w を反転させたワードを w と表す r C wq に対して rw の転置を rw r w と定義する ここで r は r と共役な複素数である r r C w w Q に対して r w r w r w r w M n に対して { w i } の転置行列 { w i と定義する を } と定義する ここで i R また つの列ベクトル u に対して内積を u u と定義する w. 局所関数の行列表示 状態スコープ幅 n の局所関数 : Q n Q からド ブル-チングラフを次のよう n 作る グラフのノ-ドの集合は Q とする ノ -ド n からノ-ド n のエッジに n の値を付ける グラフは有向グラフである このグラフの状態 遷移行列を と書く この行列のサイズは n n モノイドに加法or を入 れ 加法 乗法に分配の法則を用いてQ から記号列上の非可換環 R が自然に定義される は R 上の行列である 例. 状態スコープ幅 の局所関数 y の行列表現 は. 並列写像の性質 並列写像の単射性 全射性を判定するアルゴリズムは 次元のセルオートマトンに限り 知られている [] 次元以上のセルオートマトンではそのようなアルゴリズムは存在しないことが知られている [] 定理. を 状態 スコープ幅 n の局所関数とする とする は単射であるとき次の命題が成り立つ は唯一の非零の固有値 を持つ n rn となる最小の正の整数を とすると u ここで と u はそれぞれ の固有値 の列固有ベクトルと行固有ベクトルである またそれらの内積は u = 注意. 上記の定理は局所関数のスコープ幅 n には無関係で状態数 だけで決まる - -

3 例. 単射である例を示す を状態遷移行列とする の列固有ベクトルと行固有ベクトルを求めると次のようになる また 行ベクトルと列ベクトルの内積は 並列写像が定数対 写像とは適当な正の整数 に対して 任意の様相の並列写像による原像の集合の個数が常に 個になることである が で置換的であるとは 以外の変数を固定して のみの 変数関数としたときそれが置換的 単射 になることである [] 命題. を 状態スコープ幅 n の局所関数とする n が で置換的でかつ n で置換的ならば は n 対 写像である 定理. を正の整数とする y y od の線形局所関数の並列写像は 対 写像であり はスペクトル分解される P とおくと - -

4 I P P P ここで P I G { P } は可換群 従って 各 p は同時に対角化され 次式のようにスペクトル分解される P e i / i / i / e e より i / i / i / P e e e I ここで 故に P e i / e 5 セルオートマトンの直和 i / ここで e i / とおくと 定義 } M Q B { } M に対して BMn Q Q は B { i n Q B B n i i で与えられる ここで ib B B nn i i n 性質. テンソル積は次の性質を持つ B C B C B C C B C B C D C BD B B 5 r B r rb 6 B B i i ここで i は のi 番目の固有値である とする つの 次元セルオートマトンC Z Q n と C Z Q n の直和は次のように与えられる C C= Z Q Q n n その状態遷移行列は で与えられる ここで右辺はテンソル 積である 性質. である を 対 写像 を 対 写像のとき は 対 写像 例. y y od をスコープ幅 の線形局所関数とし を考える 対 写像の直和なので並列写像は 対 写像である で符号化する - -

5 と状態遷移行列は の つの固有値 は でこれらの固有ベクトル は i i より 直和の遷移行列はテンソル積で表されるので の つの固有値は 性質 の より が成立 一方 のスペクトル分解は 定理. を 状態スコープ幅 n の局所関数とする のとき次の命題は等価である は全射である は固有値 を持つ 系. 並列写像は単射であれば全射である 例. 定数対 写像でない全射の例 - 5 -

6 より 固有値 と の固有ベクトルはヌルワードで表現される 次に固有値 の固有ベクトルを求める は を満たす任意のノンゼロの式 z を次式で定義すると z の固有ベクトルは z z となる 6. 参考文献 [] S. oroso nd Y. N. P Deision proedures or sureiiy nd ineiiy o prllel ps or essellion sruures. J.Copu.Syses Si [] G.. Hedlund ndoorphiss nd uoorphiss o shi dynil syses. Mheil syses Theory [] J. Kri Reersiiliy nd sureiiy proles o ellulr uo J. Copu.Syse Si