Krohn – Rhodesova teorie - Krohn–Rhodes theory
v matematika a počítačová věda, Krohn – Rhodesova teorie (nebo teorie algebraických automatů) je přístup ke studiu konečných poloskupiny a automaty který se je snaží rozložit na elementární komponenty. Tyto komponenty odpovídají konečnému neperiodické poloskupiny a konečný jednoduché skupiny které jsou kombinovány dohromady způsobem bez zpětné vazby (tzv.věnec produkt "nebo" kaskáda ").
Krohn a Rhodos našel obecný rozklad pro konečné automaty. Ve svém výzkumu však autoři objevili a prokázali neočekávaný hlavní výsledek v teorii konečné semigroup, odhalující hluboké spojení mezi konečnými automaty a semigroup.
Definice a popis Krohn-Rhodesovy věty
A poloskupina S to je homomorfní obrázek a podskupina z T se říká, že je dělitel z T.
The Krohn – Rhodosova věta pro konečné semigrafy uvádí, že každá konečná poloskupina S je dělitelem konečného střídání věnec produkt konečný jednoduché skupiny, každý dělitel Sa konečný neperiodické poloskupiny (které neobsahují žádné netriviální podskupiny ).[1]
Ve formulaci automatů je Krohn – Rhodesova věta o konečných automatech uvádí, že vzhledem k konečný automat A se státy Q a vstupní sada Já, výstupní abeceda U, pak lze rozšířit stavy na Q ' takový, že nový automat A' vkládá se do kaskády „jednoduchých“, neredukovatelných automatů: Zejména A je emulován kaskádou dopředných automatů (1), jejichž přechodové poloskupiny jsou konečné jednoduché skupiny a (2) automaty, které jsou bankami žabky běží paralelně.[poznámka 1] Nový automat A' má stejné vstupní a výstupní symboly jako A. Zde mají jak stavy, tak vstupy kaskádových automatů velmi speciální hierarchický souřadnicový tvar.
Navíc každá jednoduchá skupina (primární) nebo neskupinová neredukovatelná semigroup (subsemigroup of flip-flop monoid ), která rozděluje transformační poloskupinu z A musí rozdělit přechodovou poloskupinu některé složky kaskády a pouze prvočísla, která musí nastat jako dělitele složek, jsou ta, která dělí A'přechodová poloskupina.
Složitost skupiny
The Složitost Krohn – Rhodos (také zvaný skupinová složitost nebo prostě složitost) konečné poloskupiny S je nejmenší počet skupin v a věnec produkt z konečné skupiny a konečné neperiodické semigroup S je dělitel.
Všechny konečné neperiodické poloskupiny mají složitost 0, zatímcotriviální konečné skupiny mají složitost 1. Ve skutečnosti existují poloskupiny všech nezáporných celé číslo složitost. Například pro všechny n větší než 1, multiplikativní semigroup všech (n+1)×(n+1) horní trojúhelníkový matice přes jakoukoli pevnou konečnou pole má složitost n (Kambites, 2007).
Hlavním otevřeným problémem teorie konečných poloskupin je rozhodnutelnost složitosti: existuje algoritmus který vypočítá Krohnovu-Rhodesovu složitost konečné poloskupiny, vzhledem k její násobilka Byly získány horní hranice a stále přesnější spodní hranice složitosti (viz např. Rhodes & Steinberg, 2009). Rhodes se domníval, že problém je rozhodující.[pozn. 2]
Historie a aplikace
Na konferenci v roce 1962 Kenneth Krohn a John Rhodes oznámil způsob rozložení a (deterministický) konečný automat do „jednoduchých“ komponent, které jsou samy o sobě konečnými automaty. Tato společná práce, která má důsledky pro filozofii, obsahovala jak Krohnovu disertační práci na Harvardská Univerzita a Rhodesova disertační práce na MIT.[pozn. 3] Od té doby byly publikovány jednodušší důkazy a zobecnění věty na nekonečné struktury (viz kapitola 4 knihy Steinberg a Rhodes z roku 2009 The q-Teorie konečných poloskupin pro přehled).
V článku z roku 1965 Krohna a Rhodese, důkaz věty o rozkladu konečných automatů (nebo ekvivalentně sekvenční stroje ) rozsáhle využívaly algebraiku poloskupina struktura. Pozdější důkazy obsahovaly hlavní zjednodušení pomocí konečných výrobky z věnců konečných transformačních poloskupin. Věta zobecňuje Jordan – Hölderův rozklad pro konečné skupiny (ve kterých prvočísla jsou konečné jednoduché skupiny), na všechny poloskupiny konečné transformace (pro něž jsou prvočísla opět konečné jednoduché skupiny plus všechny podskupiny „klopného obvodu“ (viz výše)). Skupinový i obecnější rozklad konečných automatů vyžaduje rozšíření sady stavů obecné, ale umožňují stejný počet vstupních symbolů. Obecně se jedná o vložené do větší struktury s hierarchickým „souřadným systémem“.
Člověk musí být opatrný v chápání pojmu „prvočíslo“, protože Krohn a Rhodes výslovně odkazují na svou větu jako „větu o primárním rozkladu“ pro automaty. Složky v rozkladu však nejsou prvotřídními automaty (s primární definováno naivně); spíše pojem primární je sofistikovanější a algebraický: poloskupiny a skupiny spojené se základními automaty rozkladu jsou primární (nebo neredukovatelné) v přísném a přirozeném algebraickém smyslu s ohledem na produkt věnce (Eilenberg, 1976). Na rozdíl od dřívějších vět o rozkladu také Krohn – Rhodesovy rozklady obvykle vyžadují rozšíření množiny stavů, takže rozšířený automat pokrývá (emuluje) rozložený. Tato fakta způsobila, že teorém bylo obtížné pochopit a bylo obtížné jej prakticky aplikovat - až donedávna, kdy byly k dispozici výpočetní implementace (Egri-Nagy a Nehaniv 2005, 2008).
H.P. Zeiger (1967) se ukázal jako důležitá varianta zvaná rozklad holonomy (Eilenberg 1976).[pozn. 4] Metoda holonomy se jeví jako relativně účinná a byla výpočetně implementována A. Egri-Nagyem (Egri-Nagy & Nehaniv 2005).
Meyer a Thompson (1969) uvádějí verzi rozkladu Krohn – Rhodes pro konečné automaty, která je ekvivalentní rozkladu, který dříve vyvinuli Hartmanis a Stearns, ale pro užitečné rozklady je pojem rozšiřování stavová sada původního automatu je nezbytná (pro případ nepermutačních automatů).
Nyní existuje mnoho důkazů a konstrukcí Krohn – Rhodesových rozkladů (např. [Krohn, Rhodes & Tilson 1968], [Ésik 2000], [Diekert et al. 2012]), přičemž holonomická metoda je obecně nejpopulárnější a nejúčinnější (i když ne ve všech případech). Vzhledem k úzkému vztahu mezi monoidy a Kategorie, je použitelná verze Krohn-Rhodesovy věty teorie kategorií. Toto pozorování a důkaz analogického výsledku poskytl Wells (1980).[pozn. 5]
Krohn – Rhodesova věta pro semigroup / monoidy je obdobou Jordan – Hölderova věta pro konečné skupiny (spíše pro poloskupiny / monoidy než pro skupiny). Věta jako taková je hlubokým a důležitým výsledkem teorie semigroup / monoidů. Věta byla také překvapivá pro mnoho matematiků a počítačových vědců[pozn. 6] protože se dříve široce věřilo, že poloskupinové / monoidní axiomy jsou příliš slabé na to, aby připustily větu o struktuře jakékoli síly, a předchozí práce (Hartmanis & Stearns) dokázala ukázat mnohem přísnější a méně obecné výsledky rozkladu pro konečné automaty.
Práce Egri-Nagye a Nehaniva (2005, 2008–) pokračuje v další automatizaci holonomické verze rozkladu Krohn – Rhodes rozšířené o související rozklad pro konečné skupiny (tzv. Frobenius – Lagrangeovy souřadnice ) za použití počítačový algebraický systém MEZERA.
Aplikace mimo semigroupové a monoidní teorie jsou nyní výpočetně proveditelné. Zahrnují výpočty v biologie a biochemické systémy (např. Egri-Nagy a Nehaniv 2008), umělá inteligence, konečný stav fyzika, psychologie, a herní teorie (viz například Rhodes 2009).
Viz také
Poznámky
- ^ Holcombe (1982), str. 141–142
- ^ Flip-flop je dvoustavový automat se třemi vstupními operacemi: identita (která ponechává svůj stav beze změny) a dvě operace resetování (které přepíšou aktuální stav resetováním na konkrétní jeden ze dvou stavů). To lze považovat za jedno-bit paměťová jednotka pro čtení a zápis: identita odpovídá čtení bitu (přičemž jeho hodnota zůstává nezměněna) a dva se resetují na nastavení hodnoty bitu na 0 nebo 1. Všimněte si, že reset je nevratný operátor, protože ničí aktuálně uložená bitová hodnota. Pozn .: Poloskupina klopného obvodu a všechny jeho podskupiny jsou neredukovatelné.
- ^ J. Rhodes, hlavní přednáška na mezinárodní konferenci o pologrupách a algebraickém inženýrství (Aizu, Japonsko ), 26. března 1997.
- ^ Morris W. Hirsch „Předmluva k Rhodosu Aplikace teorie automatů a algebry". V J. Rhodes, Aplikace teorie automatů a algebry: prostřednictvím matematické teorie složitosti k biologii, fyzice, filozofii a hrám “, (ed. C. L. Nehaniv), World Scientific Publishing Co., 2010.
- ^ Eilenberg 1976, stejně jako Dömösi a Nehaniv, 2005, předkládají důkazy opravující chybu v Zeigerově práci.
- ^ Viz také (Tilson 1989)
- ^ C.L. Nehaniv, Předmluva k (Rhodes, 2009)
Reference
- Barrington, David A. Mix (1992). "Některé problémy týkající se Razborov-Smolenského polynomů". v Paterson, M.S. (vyd.). Složitost booleovské funkce, Sel. Pap. Symp., Durham / UK 1990. Série přednášek z London Mathematical Society. 169. 109–128. ISBN 978-0-521-40826-4. Zbl 0769.68041.
- Diekert, Volker; Kufleitner, Manfred; Steinberg, Benjamin (2012). „Krohn-Rhodesova věta a místní dělitelé“. 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). Algebraická teorie sítí automatů: Úvod. Monografie SIAM o diskrétní matematice a aplikacích. Společnost pro průmyslovou a aplikovanou matematiku. 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“, v 9. mezinárodní Konference o implementaci a aplikaci automatů (CIAA 2004), Kingston, Kanada, 22. – 24. Července 2004, Revised Selected Papers, Redaktoři: Domaratzki, M .; Okhotin, A .; Salomaa, K .; et al.; Springer Přednášky z informatiky, Sv. 3317, s. 315–316, 2005
- Egri-Nagy, Attila; Nehaniv, Chrystopher L. (léto 2008). „Hierarchické souřadnicové systémy pro porozumění složitosti a jejímu vývoji s aplikacemi v genetických regulačních sítích“ (PDF). Umělý život. 14 (3): 299–312. doi:10.1162 / artl.2008.14.3.14305. ISSN 1064-5462. PMID 18489252.
- Eilenberg, Samuel (1976). Automaty, jazyky a stroje. Čistá a aplikovaná matematika, Přednášky z matematiky. New York: Academic Press. ISBN 978-0-12-234001-7. Dvě kapitoly napsal Bret Tilson.
- Ésik, Z. (březen 2000). „Důkaz věty o rozkladu Krohn – Rhodos“. Teoretická informatika. 234 (1–2): 287–300. doi:10.1016 / s0304-3975 (99) 00315-1. ISSN 0304-3975.
- Hartmanis, Juris; Stearns, R. E. (1966). Teorie algebraické struktury sekvenčních strojů. Prentice – Hall. JAKO V B0006BNWTE.
- Holcombe, W.M.L. (1982). Teorie algebraických automatů. Cambridge studia pokročilé matematiky. 1. Cambridge University Press. ISBN 978-0-521-60492-5. Zbl 0489.68046.
- Kambites, Mark (2007). „O složitosti Krohnovo-Rhodosových poloskupin horních trojúhelníkových matic“. International Journal of Algebra and Computation. 17 (1): 187–201. CiteSeerX 10.1.1.657.4000. doi:10.1142 / S0218196707003548. ISSN 0218-1967.
- Krohn, K. R .; a Rhodes, J. L. (1962), „Algebraická teorie strojů“, Proceedings of the Symposium on Mathematical Theory of Automata (redaktor: Fox, J.), (Wiley – Interscience )
- Krohn, Kenneth; Rhodes, John (duben 1965). „Algebraická teorie strojů. I. Věta o primárním rozkladu pro konečné semigroup a stroje“ (PDF). Transakce Americké matematické společnosti. 116: 450–464. doi:10.2307/1994127. ISSN 0002-9947. JSTOR 1994127. Citováno 18. září 2010.
- Krohn, Kenneth; Rhodes, John L. (srpen 1968). Arbib, Michael A. (ed.). Algebraická teorie strojů, jazyků a poloskupin. Akademický tisk. ISBN 978-0-12-059050-6.
- Lallement, Gerard (01.03.1971). "Věta o primárním rozkladu pro konečné monoidy". Teorie výpočetních systémů. 5 (1): 8–12. doi:10.1007 / BF01691462. ISSN 1433-0490.
- Meyer, A. R .; Thompson, C. (01.06.1969). „Poznámky k algebraickému rozkladu automatů“ (PDF). Teorie výpočetních systémů. 3 (2): 110–118. CiteSeerX 10.1.1.649.4716. doi:10.1007 / BF01746516. ISSN 1432-4350.
- John Rhodes; Benjamin Steinberg (2008-12-17). Teorie q konečných pologrup. Springer Verlag. ISBN 978-0-387-09780-0.
- Straubing, Howard; Thérien, Denis (2002). „Slabě iterované blokové produkty konečných monoidů“. V Raisbaum, Sergio (ed.). Přednášky z informatiky. LATIN 2002: Teoretická informatika. 2286. Berlín: Springer. str. 91–104. doi:10.1007/3-540-45995-2_13. ISBN 978-3-540-43400-9. Citováno 18. září 2010.
- Rhodes, John L. (3. září 2009). Nehaniv, Chrystopher L. (ed.). Aplikace teorie automatů a algebry prostřednictvím matematické teorie složitosti ve fyzice, biologii, filozofii a hrách konečných stavů. Singapur: Světová vědecká nakladatelská společnost. ISBN 978-981-283-696-0.
- Tilson, Bret (září 1987). „Kategorie jako algebra: základní složka v teorii monoidů“. 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). „Věta Krohn – Rhodes pro kategorie“. Journal of Algebra. 64: 37–45. doi:10.1016/0021-8693(80)90130-1. ISSN 0021-8693.
- Zeiger, H. P. (duben 1967). "Kaskádová syntéza konečných stavových strojů". Informace a kontrola. 10 (4): 419–433. doi:10.1016 / S0019-9958 (67) 90228-8. ISSN 1462-3889. Erratum: Informace a kontrola 11(4): 471 (1967), plus erratum.
Další čtení
- Rhodes, John L. (2010). Chrystopher L. Nehaniv (ed.). Aplikace teorie automatů a algebry: prostřednictvím matematické teorie složitosti v biologii, fyzice, psychologii, filozofii a hrách. World Scientific Pub Co Inc. ISBN 978-981-283-696-0.
- Rhodes, Johne; Steinberg, Benjamin (17. 12. 2008). Teorie q konečných pologrup. Springer Verlag. ISBN 978-0-387-09780-0.
- Straubing, Howard (1994). Konečné automaty, formální logika a složitost obvodů. Pokrok v teoretické informatice. Basilej: Birkhäuser. ISBN 978-3-7643-3719-3. Zbl 0816.68086.
externí odkazy
- Profesor John L. Rhodes, webová stránka Kalifornské univerzity v Berkeley
- SgpDec: Hierarchické složení a rozklad permutačních skupin a transformačních poloskupin, vyvinutý společností A. Egri-Nagy a C. L. Nehaniv. Softwarový balíček s otevřeným zdrojovým kódem pro Počítačový algebraický systém GAP.
- John L. Rhodes (2010). Chrystopher L. Nehaniv (ed.). Aplikace teorie automatů a algebry: prostřednictvím matematické teorie složitosti v biologii, fyzice, psychologii, filozofii a hrách. World Scientific Pub Co Inc. ISBN 978-981-283-696-0.
- Úvod do Krohn-Rhodesovy věty (Oddíl 5); součást průzkumu složitosti MOOC v institutu Santa Fe Institute Úvod do renormalizace Simon DeDeo.