クローン–ローズの定理とは？わかりやすく解説

数学とコンピュータサイエンスにおいて、クローン–ローズ理論（Krohn–Rhodes theory、代数オートマトン理論）は、有限半群とオートマトンを基本成分に分解する研究手法である。これらの成分は、フィードバックなしで結合された有限非周期半群と有限単純群に対応する（「リース積」または「カスケード」と呼ばれる）。

クローンとローズは有限オートマトンに対する一般的な分解を発見した。著者らは有限半群論における予想外の重要な結果を発見し、証明し、有限オートマトンと半群の間に深いつながりがあることを明らかにした。

クローン・ローズ定理の定義と説明

T を半群とする。T の部分半群の準同型像である半群 S は、T の因子であるという。

有限半群のクローン・ローズの定理は、すべての有限半群Sは、Sの約数である有限単純群と有限非周期半群（非自明な部分群を含まない）の有限交代花輪積の約数であることを述べている。^[1]

オートマトン定式化において、有限オートマトンに対するクローン・ローズ定理は、状態 Q と入力集合 I、出力アルファベット U を持つ有限オートマトン A が与えられたとき、状態を Q' に拡張して、新しいオートマトン A' を「単純」で既約なオートマトンカスケードに埋め込むことができると述べています。具体的には、A は (1) 変換半群が有限単純群であるオートマトンと (2) 並列に実行されるフリップフロップのバンクであるオートマトンからなるフィードフォワードカスケードによってエミュレートされます。^{[nb 1]} 新しいオートマトン A' は A と同じ入力シンボルと出力シンボルを持ちます。ここで、カスケードされたオートマトンの状態と入力はどちらも非常に特殊な階層座標形式を持ちます。

さらに、A の変換半群を分割する各単純群（素数）または非群既約半群（フリップフロップモノイドの部分半群）は、カスケードの何らかのコンポーネントの変換半群を分割する必要があり、コンポーネントの約数として発生する必要がある素数のみが A の変換半群を分割する素数です。

グループの複雑さ

有限半群 S のクローン・ローズ複雑度（群複雑度または単に複雑度とも呼ばれる）は、S が約数である有限群と有限非周期半群の輪積内の群の最小数です。

すべての有限非周期半群の計算量は0ですが、非自明な有限群の計算量は1です。実際、あらゆる非負整数の計算量を持つ半群が存在します。例えば、1より大きい任意のnに対して、任意の固定有限体上のすべての(n+1)×(n+1)上三角行列の乗法半群の計算量はnです（Kambites, 2007）。

有限半群論における主要な未解決問題は、計算量の決定可能性である。すなわち、乗算表が与えられた有限半群のクローン・ローズ計算量を計算できるアルゴリズムは存在するのだろうか？計算量の上限値と、より正確な下限値が既に得られている（例えば、Rhodes & Steinberg, 2009を参照）。ローズは、この問題が決定可能であると予想している。^[2]

歴史と応用

1962年の会議で、ケネス・クローンとジョン・ローズは、（決定論的）有限オートマトンを、それ自体が有限オートマトンである「単純な」構成要素に分解する方法を発表しました。哲学にも影響を与えるこの共同研究は、クローンのハーバード大学における博士論文とローズのMITにおける博士論文の両方から構成されています。^[3] より単純な証明や、この定理の無限構造への一般化は、その後も発表されています（概要については、ローズとスタインバーグの2009年の著書『有限半群のq理論』第4章を参照）。

1965年のクローンとローズの論文では、有限オートマトン（あるいは等価な逐次機械）の分解に関する定理の証明において、代数的半群構造が広範に用いられた。後の証明では、有限変換半群の有限花輪積を用いた大幅な簡略化が行われた。この定理は、有限群（素数は有限単純群である）に対するジョルダン・ヘルダー分解を、すべての有限変換半群（素数は有限単純群と「フリップフロップ」（上記参照）のすべての部分半群である）に一般化する。群分解とより一般的な有限オートマトン分解はどちらも、一般の分解の状態集合を拡張する必要があるが、入力記号の数は同数で済む。一般の場合、これらは階層的な「座標系」を持つより大きな構造に埋め込まれる。

クローンとローズは、自らの定理をオートマトンにおける「素数分解定理」と明確に呼んでいるため、「素数」の概念を理解する際には注意が必要である。しかし、分解の構成要素は素数オートマトン（素数が単純に定義されている）ではない。むしろ、素数の概念はより洗練され、代数的なものである。分解を構成するオートマトンに関連付けられた半群と群は、花輪積に関して厳密かつ自然な代数的意味で素数（または既約）である（Eilenberg, 1976）。また、以前の分解定理とは異なり、クローン・ローズ分解では通常、状態集合の拡張が必要となるため、拡張されたオートマトンが分解対象のオートマトンを覆い（エミュレートし）、それを模倣する。これらの事実により、定理は理解が難しく、実際的な適用が困難でしたが、最近になって計算実装が可能になってからは状況は変わりました (Egri-Nagy & Nehaniv 2005、2008)。

H.P. ジーゲル (1967) は、ホロノミー分解 (エリンバーグ1976) と呼ばれる重要な変形を証明した。^{[nb 2]}

ホロノミー法は比較的効率的であると思われ、A. イグリナギー (イグリナギー & ナハニブ2005) によって計算機に実装された。

マイヤーとトンプソン (1969) は、ハートマニスとスターンズが以前に開発した分解と同等の有限オートマトン用のクローン-ローズ分解のバージョンを与えているが、有用な分解のためには、元のオートマトンの状態セットを拡張するという概念が不可欠である (非順列オートマトンの場合)。

クローン・ローズ分解には現在、多くの証明と構成法が存在する（例えば、[クローン,ローズ& ティルソン1968]、[エシク2000]、[ディカートet al. 2012]）。その中でも、ホロノミー法は最も一般的で、一般的には効率的である（ただし、すべての場合に当てはまるわけではない）。[ツマーマン2010][1]は、この定理の初等的な証明を与えている。モノイドと圏論の密接な関係により、クローン・ローズ定理の一種は圏論にも適用可能である。この観察と類似の結果の証明は、Wells (1980) によって提示された。^{[nb 3]}

半群／モノイドに対するクローン＝ローズ定理は、有限群に対するジョルダン＝ヘルダー定理（群ではなく半群／モノイドに対する）の類似物である。そのため、この定理は半群／モノイド理論における奥深く重要な結果である。この定理は多くの数学者やコンピュータ科学者にとっても驚くべきものであった。^{[nb 4]}なぜなら、それまで半群／モノイド公理は構造定理として成立するには弱すぎると広く信じられていたためであり、先行研究（ハートマニスとスターンズ）では有限オートマトンに対して、はるかに厳格で一般性の低い分解結果しか示せなかったからである。

イグリナギーとネハニブ(2005、2008-) による研究では、コンピュータ代数システム GAP を使用して、有限群の関連する分解 (いわゆるフロベニウス-ラグランジュ座標) を拡張した -Rhodes 分解のホロノミーバージョンをさらに自動化し続けています。

半群理論とモノイド理論以外の応用も、現在では計算的に可能となっています。これには、生物学および生化学システム（例：イグリナギー & ネハニブ 2008）、人工知能、有限状態物理学、心理学、ゲーム理論（例：Rhodes 2009）における計算が含まれます。

参照

半群作用
変換半群
グリーン関係式

注

^ Holcombe (1982) pp. 141–142
^ J. Rhodes, Keynote talk at the International Conference on Semigroups & Algebraic Engineering (Aizu, Japan), 26 March 1997.
^ Morris W. Hirsch, "Foreword to Rhodes' Applications of Automata Theory and Algebra". In J. Rhodes, Applications of Automata Theory and Algebra: Via the Mathematical Theory of Complexity to Biology, Physics, Philosophy and Games", (ed. C. L. Nehaniv), World Scientific Publishing Co., 2010.

^ フリップフロップは、3つの入力操作を持つ2状態オートマトンです。1つは恒等演算（状態を変更しない）で、もう1つは2つのリセット演算（現在の状態を2つの状態のうちの特定の状態にリセットすることで上書きする）です。これは1ビットの読み書き可能な記憶装置と考えることができます。恒等演算はビットの読み取り（値は変更しない）に対応し、2つのリセットはビットの値を0または1に設定することに対応します。リセットは現在格納されているビット値を破壊するため、不可逆な演算であることに注意してください。注：フリップフロップの半群とそのすべての部分半群は既約です。
^ Ailenberg 1976、Dömösi および Nehaniv、2005 は、Zeiger の論文の誤りを訂正する証明を示しています。
^ 参照（Tilson 1989）
^ C.L. Nehaniv, Preface to (Rhodes, 2009)

参考文献

Barrington, David A. Mix (1992). “Some problems involving Razborov-Smolensky polynomials”. In Paterson, M.S.. Boolean function complexity, Sel. Pap. Symp., Durham/UK 1990. London Mathematical Society Lecture Notes Series. 169. pp. 109–128. ISBN 978-0-521-40826-4. Zbl 0769.68041
Diekert, Volker; Kufleitner, Manfred; Steinberg, Benjamin (2012). “The Krohn-Rhodes Theorem and Local Divisors”. Fundamenta Informaticae 116 (1–4): 65–77. arXiv:1111.1585. doi:10.3233/FI-2012-669. ISSN 0169-2968.
Pál Dömösi; Chrystopher L. Nehaniv (2005). Algebraic Theory of Automata Networks: An Introduction. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics. ISBN 978-0-89871-569-9
Egri-Nagy, A.; and Nehaniv, C. L. (2005), "Algebraic Hierarchical Decomposition of Finite State Automata: Comparison of Implementations for Krohn–Rhodes Theory", in 9th International Conference on Implementation and Application of Automata (CIAA 2004), Kingston, Canada, July 22–24, 2004, Revised Selected Papers, Editors: Domaratzki, M.; Okhotin, A.; Salomaa, K.; et al.; Springer Lecture Notes in Computer Science, Vol. 3317, pp. 315–316, 2005
Egri-Nagy, Attila; Nehaniv, Chrystopher L. (Summer 2008). “Hierarchical Coordinate Systems for Understanding Complexity and its Evolution with Applications to Genetic Regulatory Networks”. Artificial Life 14 (3): 299–312. doi:10.1162/artl.2008.14.3.14305. hdl:2299/16600. ISSN 1064-5462. PMID 18489252.
Eilenberg, Samuel (1976). Automata, Languages and Machines. Pure and applied mathematics, Lecture notes in mathematics. New York: Academic Press. ISBN 978-0-12-234001-7 Two chapters are written by Bret Tilson.
Ésik, Z. (March 2000). “A proof of the Krohn–Rhodes decomposition theorem”. Theoretical Computer Science 234 (1–2): 287–300. doi:10.1016/s0304-3975(99)00315-1. ISSN 0304-3975.
Hartmanis, Juris; Stearns, R. E. (1966). Algebraic structure theory of sequential machines. Prentice–Hall. ASIN B0006BNWTE
Holcombe, W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. 1. Cambridge University Press. ISBN 978-0-521-60492-5. Zbl 0489.68046
Kambites, Mark (2007). “On the Krohn–Rhodes complexity of semigroups of upper triangular matrices”. International Journal of Algebra and Computation 17 (1): 187–201. doi:10.1142/S0218196707003548. ISSN 0218-1967.
Krohn, K. R.; and Rhodes, J. L. (1962), "Algebraic theory of machines", Proceedings of the Symposium on Mathematical Theory of Automata (editor: Fox, J.), (Wiley–Interscience)
Krohn, Kenneth; Rhodes, John (April 1965). “Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines”. Transactions of the American Mathematical Society 116: 450–464. doi:10.2307/1994127. ISSN 0002-9947. JSTOR 1994127 2010年9月18日閲覧。.
Krohn, Kenneth; Rhodes, John L. (August 1968). Arbib, Michael A.. ed. Algebraic Theory of Machines, Languages and Semigroups. Academic Press. ISBN 978-0-12-059050-6
Lallement, Gerard (1971-03-01). “On the prime decomposition theorem for finite monoids”. Theory of Computing Systems 5 (1): 8–12. doi:10.1007/BF01691462. ISSN 1433-0490.
Meyer, A. R.; Thompson, C. (1969-06-01). “Remarks on algebraic decomposition of automata”. Theory of Computing Systems 3 (2): 110–118. doi:10.1007/BF01746516. ISSN 1432-4350.
John Rhodes; Benjamin Steinberg (2008-12-17). The q-theory of finite semigroups. Springer Verlag. ISBN 978-0-387-09780-0
Straubing, Howard; Thérien, Denis (2002). "Weakly iterated block products of finite monoids". In Raisbaum, Sergio (ed.). Lecture Notes in Computer Science. LATIN 2002: Theoretical Informatics. Vol. 2286. Berlin: Springer. pp. 91–104. doi:10.1007/3-540-45995-2_13. ISBN 978-3-540-43400-9. 2010年9月18日閲覧。
Rhodes, John L. (September 3, 2009). Nehaniv, Chrystopher L.. ed. Applications of Automata Theory and Algebra via the Mathematical Theory of Complexity to Finite-State Physics, Biology, Philosophy, and Games. Singapore: World Scientific Publishing Company. ISBN 978-981-283-696-0
Tilson, Bret (September 1987). “Categories as algebra: an essential ingredient in the theory of monoids”. Journal of Pure and Applied Algebra 48 (1–2): 83–198. doi:10.1016/0022-4049(87)90108-3. ISSN 0022-4049.
Wells, C. (1980). “A Krohn–Rhodes theorem for categories”. Journal of Algebra 64: 37–45. doi:10.1016/0021-8693(80)90130-1. ISSN 0021-8693.
Zeiger, H. P. (April 1967). “Cascade synthesis of finite state machines”. Information and Control 10 (4): 419–433. doi:10.1016/S0019-9958(67)90228-8. ISSN 1462-3889. Erratum: Information and Control 11(4): 471 (1967), plus erratum.