Krohn–Rhodes teori

Inom matematik och datavetenskap är Krohn –Rhodesteorin (eller algebraisk automatteorin ) ett förhållningssätt till studiet av finita semigrupper och automater som försöker bryta ner dem i termer av elementära komponenter. Dessa komponenter motsvarar ändliga aperiodiska semigrupper och ändliga enkla grupper som kombineras på ett återkopplingsfritt sätt (kallad " kransprodukt " eller "kaskad").

Krohn och Rhodos fann en allmän nedbrytning för finita automater . Men när de gjorde sin forskning upptäckte och bevisade författarna ett oväntat stort resultat i teorin om finita semigrupper, vilket avslöjade en djup koppling mellan finita automater och semigrupper.

Definitioner och beskrivning av Krohn–Rhodes sats

Låt T vara en halvgrupp. En halvgrupp S som är en homomorf bild av en delgrupp av T sägs vara en divisor av T .

Krohn -Rhodes-satsen för finita halvgrupper säger att varje finit halvgrupp S är en divisor av en finit alternerande kransprodukt av finita enkla grupper , var och en en divisor av S och finita aperiodiska halvgrupper (som inte innehåller några icke-triviala undergrupper ).

I automatformuleringen säger Krohn–Rhodes-satsen för finita automater att givet en finit automat A med tillstånd Q och ingångsmängd I , utgående alfabetet U , så kan man expandera tillstånden till Q' så att den nya automaten A' bäddas in i en kaskad av "enkla", irreducerbara automater: I synnerhet emuleras A av en feed-forward-kaskad av (1) automater vars transformationssemigrupper är ändliga enkla grupper och (2) automater som är banker av flip-flops som löper parallellt. Den nya automaten A' har samma ingångs- och utgångssymboler som A . Här har både tillstånden och ingångarna för de kaskadkopplade automaterna en mycket speciell hierarkisk koordinatform.

Dessutom måste varje enkel grupp ( primtal ) eller icke-grupp irreducerbar halvgrupp (underhalvgrupp av vippan monoid ) som delar transformationssemigruppen av A dela transformationssemigruppen för någon komponent i kaskaden, och endast de primtal som måste förekomma som delare av komponenterna är de som delar A: s transformationssemigrupp.

Gruppens komplexitet

Krohn –Rhodes-komplexiteten (även kallad gruppkomplexitet eller bara komplexitet ) för en finit halvgrupp S är det minsta antalet grupper i en kransprodukt av finita grupper och finita aperiodiska halvgrupper av vilka S är en divisor.

Alla ändliga aperiodiska semigrupper har komplexitet 0, medan icke- triviala ändliga grupper har komplexitet 1. Faktum är att det finns semigrupper av varje icke-negativ heltalskomplexitet . Till exempel, för vilket n som helst som är större än 1, har den multiplikativa semigruppen av alla ( n +1) × ( n +1) övre triangulära matriser över ett fixerat ändligt fält komplexiteten n (Kambites, 2007).

Ett stort öppet problem inom finita semigroup-teorin är avgörbarheten av komplexitet : finns det en algoritm som kommer att beräkna Krohn–Rhodes-komplexiteten för en finit semigroup, givet dess multiplikationstabell ? Övre gränser och allt mer exakta nedre gränser för komplexitet har erhållits (se t.ex. Rhodes & Steinberg, 2009). Rhodes har gissat att problemet är avgörbart.

Historik och applikationer

Vid en konferens 1962 tillkännagav Kenneth Krohn och John Rhodes en metod för att bryta ned en (deterministisk) ändlig automat i "enkla" komponenter som i sig är ändliga automater. Detta gemensamma arbete, som har implikationer för filosofin [citat eller förklaring behövs], omfattade både Krohns doktorsavhandling vid Harvard University och Rhodes doktorsavhandling vid MIT . Enklare bevis, och generaliseringar av satsen till oändliga strukturer, har publicerats sedan dess (se kapitel 4 i Rhodos och Steinbergs bok 2009 The q-Theory of Finite Semigroups för en översikt).

I 1965 års uppsats av Krohn och Rhodes gjorde beviset för satsen om nedbrytningen av finita automater (eller motsvarande sekventiella maskiner) omfattande användning av den algebraiska semigruppstrukturen . Senare bevis innehöll stora förenklingar med användning av finita kransprodukter av finita transformationssemigrupper. Satsen generaliserar Jordan–Hölder-sönderdelningen för finita grupper (där primtalen är de ändliga enkla grupperna), till alla finita transformationssemigrupper (för vilka primtalen återigen är de ändliga enkla grupperna plus alla underhalvgrupper av "vippan" ( se ovan)). Både grupp- och mer generell finita automatnedbrytning kräver att tillståndsuppsättningen för det allmänna utökas, men tillåter samma antal inmatningssymboler. I det allmänna fallet är dessa inbäddade i en större struktur med ett hierarkiskt "koordinatsystem".

Man måste vara försiktig med att förstå begreppet "primtal" eftersom Krohn och Rhodes uttryckligen hänvisar till deras teorem som ett "primärt sönderfallssats" för automater. Komponenterna i nedbrytningen är dock inte prime automater (med prime definierad på ett naivt sätt); snarare är föreställningen om prime mer sofistikerad och algebraisk: de semigrupper och grupper som är associerade med de sammansatta automaterna för nedbrytningen är prime (eller irreducerbara) i strikt och naturlig algebraisk mening med avseende på kransprodukten ( Eilenberg , 1976). Dessutom, till skillnad från tidigare sönderdelningssatser, kräver Krohn–Rhodes-nedbrytningarna vanligtvis expansion av tillståndsuppsättningen, så att den expanderade automaten täcker (emulerar) den som sönderdelas. Dessa fakta har gjort satsen svår att förstå och utmanande att tillämpa på ett praktiskt sätt – tills nyligen, när beräkningsimplementeringar blev tillgängliga (Egri-Nagy & Nehaniv 2005, 2008).

HP Zeiger (1967) bevisade en viktig variant som kallas holonominedbrytning (Eilenberg 1976). Holonomimetoden verkar vara relativt effektiv och har implementerats beräkningsmässigt av A. Egri-Nagy (Egri-Nagy & Nehaniv 2005).

Meyer och Thompson (1969) ger en version av Krohn–Rhodes-nedbrytning för finita automater som är likvärdig med den nedbrytning som tidigare utvecklats av Hartmanis och Stearns, men för användbara nedbrytningar är idén om att expandera tillståndsuppsättningen av den ursprungliga automaten väsentlig ( för automatfallet utan permutation).

Det finns nu många bevis och konstruktioner av Krohn–Rhodes nedbrytningar (t.ex. [Krohn, Rhodes & Tilson 1968], [Ésik 2000], [Diekert et al. 2012]), med holonomimetoden den mest populära och effektiva i allmänhet (även om inte i alla fall). På grund av det nära sambandet mellan monoider och kategorier är en version av Krohn-Rhodes-satsen tillämplig på kategoriteori . Denna observation och ett bevis på ett analogt resultat erbjöds av Wells (1980).

Krohn–Rhodes sats för semigrupper/monoider är en analog till Jordan–Hölders sats för ändliga grupper (för semigrupper/monoider snarare än grupper). Som sådan är satsen ett djupt och viktigt resultat i semigroup/monoid teori. Teoremet var också överraskande för många matematiker och datavetare eftersom det tidigare hade ansetts allmänt att halvgrupps/monoidaxiomen var för svaga för att erkänna en struktursats av någon styrka, och tidigare arbeten (Hartmanis & Stearns) kunde bara visa mycket styvare och mindre generella nedbrytningsresultat för finita automater.

Arbete av Egri-Nagy och Nehaniv (2005, 2008–) fortsätter att ytterligare automatisera holonomiversionen av Krohn–Rhodes-nedbrytningen utökad med den relaterade nedbrytningen för ändliga grupper (så kallade Frobenius–Lagrange-koordinater) med hjälp av datoralgebrasystemet GAP .

Tillämpningar utanför semigroup och monoid teorier är nu beräkningsmässigt genomförbara. De inkluderar beräkningar inom biologi och biokemiska system (t.ex. Egri-Nagy & Nehaniv 2008), artificiell intelligens , finita tillståndsfysik , psykologi och spelteori ( se till exempel Rhodos 2009).

Se även

• Semigruppsåtgärd
• Transformation semigrupp
• Greens relationer

Anteckningar

---

•    Barrington, David A. Mix (1992). "Några problem som involverar Razborov-Smolensky polynom". I Paterson, MS (red.). Boolesk funktionskomplexitet, Sel. Pap. Symp., Durham/UK 1990 . London Mathematical Society föreläsningsanteckningsserie. Vol. 169. s. 109–128. ISBN 978-0-521-40826-4 . Zbl 0769.68041 .
•   Diekert, Volker; Kufleitner, Manfred; Steinberg, Benjamin (2012). "Krohn-Rhodes teorem och lokala delare". 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). Algebraisk teori om automatnätverk: en introduktion . SIAM monografier om diskret matematik och tillämpningar. Föreningen för industriell och tillämpad matematik. ISBN 978-0-89871-569-9 .
• Egri-Nagy, A.; och Nehaniv, CL (2005), "Algebraic Hierarchical Decomposition of Finite State Automata: Comparison of Implementations for Krohn–Rhodes Theory", i 9:e internationella konferensen om implementering och tillämpning av automater (CIAA 2004), Kingston, Kanada, 22–24 juli , 2004, Revised Selected Papers , Redaktörer: Domaratzki, M.; Okhotin, A.; Salomaa, K.; et al. ; Springer Lecture Notes in Computer Science , Vol. 3317, s. 315–316, 2005
•    Egri-Nagy, Attila; Nehaniv, Chrystopher L. (sommaren 2008). "Hierarkiska koordinatsystem för att förstå komplexitet och dess utveckling med tillämpningar på genetiska reglerande nätverk" ( PDF) . Konstgjort liv . 14 (3): 299–312. doi : 10.1162/artl.2008.14.3.14305 . hdl : 2299/16600 . ISSN 1064-5462 . PMID 18489252 .
•   Eilenberg, Samuel (1976). Automater, språk och maskiner . Ren och tillämpad matematik, Föreläsningsanteckningar i matematik. New York: Academic Press. ISBN 978-0-12-234001-7 . Två kapitel är skrivna av Bret Tilson.
•   Ésik, Z. (mars 2000). "Ett bevis på Krohn-Rhodes nedbrytningssats" . Teoretisk datavetenskap . 234 (1–2): 287–300. doi : 10.1016/s0304-3975(99)00315-1 . ISSN 0304-3975 .
•   Hartmanis, Juris ; Stearns, RE (1966). Algebraisk strukturteori för sekventiella maskiner . Prentice–Hall. ASIN B0006BNWTE .
•    Holcombe, WML (1982). Algebraisk automatteori . Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press . ISBN 978-0-521-60492-5 . Zbl 0489.68046 .
•    Kambites, Mark (2007). "På Krohn–Rhodes komplexiteten av semigrupper av övre triangulära matriser". International Journal of Algebra and Computation . 17 (1): 187–201. CiteSeerX 10.1.1.657.4000 . doi : 10.1142/S0218196707003548 . ISSN 0218-1967 .
• Krohn, KR; och Rhodes, JL (1962), "Algebraic theory of machines", Proceedings of the Symposium on Mathematical Theory of Automata (redaktör: Fox, J.), ( Wiley–Interscience )
•    Krohn, Kenneth; Rhodes, John (april 1965). "Algebraisk teori om maskiner. I. Prime Decomposition Theorem for Finita Semigroups and Machines" ( PDF) . Transaktioner från American Mathematical Society . 116 : 450–464. doi : 10.2307/1994127 . ISSN 0002-9947 . JSTOR 1994127 . Hämtad 18 september 2010 .
•   Krohn, Kenneth; Rhodes, John L. (augusti 1968). Arbib, Michael A. (red.). Algebraisk teori om maskiner, språk och halvgrupper . Akademisk press. ISBN 978-0-12-059050-6 .
•   Lallement, Gerard (1971-03-01). "På den primära nedbrytningssatsen för finita monoider". Teori om datorsystem . 5 (1): 8–12. doi : 10.1007/BF01691462 . ISSN 1433-0490 .
•    Meyer, AR; Thompson, C. (1969-06-01). "Anmärkningar om algebraisk nedbrytning av automater" (PDF) . Teori om datorsystem . 3 (2): 110–118. CiteSeerX 10.1.1.649.4716 . doi : 10.1007/BF01746516 . ISSN 1432-4350 .
•   John Rhodes; Benjamin Steinberg (2008-12-17). Q-teorin om ändliga semigrupper . Springer Verlag. ISBN 978-0-387-09780-0 .
•   Straubing, Howard; Thérien, Denis (2002). "Svagt itererade blockprodukter av finita monoider" . I Raisbaum, Sergio (red.). Föreläsningsanteckningar i datavetenskap . LATIN 2002: Teoretisk informatik. Vol. 2286. Berlin: Springer. s. 91–104. doi : 10.1007/3-540-45995-2_13 . ISBN 978-3-540-43400-9 . Hämtad 18 september 2010 .
•   Rhodes, John L. (3 september 2009). Nehaniv, Chrystopher L. (red.). Tillämpningar av automatteori och algebra via den matematiska teorin om komplexitet till finita tillståndsfysik, biologi, filosofi och spel . Singapore: World Scientific Publishing Company. ISBN 978-981-283-696-0 .
•   Tilson, Bret (september 1987). "Kategorier som algebra: en viktig ingrediens i teorin om monoider" . 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). "En Krohn–Rhodes sats för kategorier" . Journal of Algebra . 64 : 37–45. doi : 10.1016/0021-8693(80)90130-1 . ISSN 0021-8693 .
•   Zeiger, HP (april 1967). "Kaskadsyntes av finita tillståndsmaskiner" . Information och kontroll . 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.

Vidare läsning

•   Rhodes, John L. (2010). Chrystopher L. Nehaniv (red.). Tillämpningar av automatteori och algebra: via den matematiska teorin om komplexitet till biologi, fysik, psykologi, filosofi och spel . World Scientific Pub Co Inc. ISBN 978-981-283-696-0 .
•   Rhodos, John ; Steinberg, Benjamin (2008-12-17). Q-teorin om ändliga semigrupper . Springer Verlag. ISBN 978-0-387-09780-0 .
•    Straubing, Howard (1994). Finita automater, formell logik och kretskomplexitet . Framsteg i teoretisk datavetenskap. Basel: Birkhäuser. ISBN 978-3-7643-3719-3 . Zbl 0816.68086 .

externa länkar

• Prof. John L. Rhodes, University of California i Berkeley webbsida
• SgpDec: Hierarchical Composition and Decomposition of Permutation Groups and Transformation Semigroups , utvecklad av A. Egri-Nagy och CL Nehaniv. Programpaket med öppen källkod för GAP-datoralgebrasystemet .
•   John L. Rhodes (2010). Chrystopher L. Nehaniv (red.). Tillämpningar av automatteori och algebra: via den matematiska teorin om komplexitet till biologi, fysik, psykologi, filosofi och spel . World Scientific Pub Co Inc. ISBN 978-981-283-696-0 .
• En introduktion till Krohn-Rhodes teorem (avsnitt 5); del av Santa Fe Institute Complexity Explorer MOOC Introduction to Renormalization , av Simon DeDeo.