強連結オートマトンとその商オートマトンの自己同形群
スポンサーリンク
概要
- 論文の詳細を見る
強連結オートマトンAにおける構造半群ℰ(A)の極小べき等元ℯから得られる群ℯ𝒞(A)ℯは, Aの自己同形群𝒜(A)と重要なかかわりをもっていることが知られている. 本論文ではℯ𝒞(A)ℯを用いて, Aの自己同形群構成に関する結果とAの商オートマトンに関する新たな結果を示す. 強連結オートマトンAの自己同形群は, ℯ𝒞(A)ℯの部分群の準同形像となることが知られている. 特に極小べき等元による状態集合の像{Xℯ}ℯ∈E_0(E_0は極小べき等元全体の集合)が, 状態集合の分割を導くときにはℯ𝒞(A)ℯの中心化群と同形になる.本論文ではまずこれらの結果を, {Xℯ}が状態集合の被覆となっている場合に拡張させることを考える.そのために基本分割の概念を導入する.そしてXℯ上の置換群ℯ𝒞3(A)ℯの中心化群の元で, Xℯに属する基本分割の同値類を固定しているものの全体が, 𝒜(A)と同形になることを示す.これはBarnesによる自己同形群となるための条件をより具体的に述べたもので, 自己同形群の有効的な構成方法を得るための手掛りを与えるものとなっている.次に商オートマトンの場合の自己同形群について考える.任意の有限群G, Hに対して, Gと同形な自己同形群𝒜(A)をもつ強連結オートマトンで, 商オートマトンA/𝒜(A)の自己同形群がHに同形なものが存在することが知られている. 本論文ではA/𝒜(A)の自己同形群はℯ𝒞(A)ℯの部分群の準同形像となることを示す. これにより, 𝒜(A)による商オートマトンの自己同形群は𝒜(A)とは独立であるが, ℯ𝒞(A)ℯに関係していることがわかる. また, 商オートマトンの基本分割は元のオートマトンの基本分割と本質的には変わらないことを示す.
- 社団法人電子情報通信学会の論文
- 1996-03-25
著者
関連論文
- 年長園児における加法逆減法問題の理解度 : 自己を含む場合と他者のみの場合の比較
- ある種の非サイクル的有向グラフに対する極大パス被覆問題の並列計算量
- ある種の非サイクル的有向グラフの極大パス被覆を与える線形時間アルゴリズム
- 有向グラフに対する極大パスカバー問題の計算量(計算量理論とその周辺)
- Complexity of Path Covering Problems in Acyclic Alternate Graphs II(Algorithms : Mathematical Foundations and Applications)
- COMPLEXITY OF PATH COVERING PROBLEMS IN ACYCLIC ALTERNATE GRAPHS(Mathematical Foundations of Computer Science and Their Applications)
- 米国算数教科書紹介(7)
- 米国算数教科書紹介(VI)
- 米国算数教科書紹介(V)
- 米国算数教科書紹介(IV)
- 米国算数教科書紹介(III)
- 米国算数教科書紹介(II)
- 米国算数教科書紹介(I)
- 強連結オートマトンとその商オートマトンの自己同型群(計算量理論の諸相 : その基礎的研究)
- 強連結オートマトンとその商オートマトンの自己同形群
- 商オートマトンの自己同型群について
- ニ部グラフの最長初等道と最長初等閉路について (形式言語理論とオートマトン理論)
- B2 年長園児における加法逆減法問題の理解度 : 自己を含む場合と他者のみの場合の比較(B 問題解決(1)(問題解決・指導法等),論文発表の部)