Krohn–Rhodes theory

In mathematics and computer science, the Krohn–Rhodes theory (or algebraic automata theory) is an approach to the study of finite semigroups and automata that seeks to decompose them in terms of elementary components. These components correspond to finite aperiodic semigroups and finite simple groups that are combined in a feedback-free manner (called a "wreath product" or "cascade").

Krohn and Rhodes found a general decomposition for finite automata. The authors discovered and proved an unexpected major result in finite semigroup theory, revealing a deep connection between finite automata and semigroups.

Definitions and description of the Krohn–Rhodes theorem

Let T be a semigroup. A semigroup S that is a homomorphic image of a subsemigroup of T is said to be a divisor of T.

The Krohn–Rhodes theorem for finite semigroups states that every finite semigroup S is a divisor of a finite alternating wreath product of finite simple groups, each a divisor of S, and finite aperiodic semigroups (which contain no nontrivial subgroups).[1]

In the automata formulation, the Krohn–Rhodes theorem for finite automata states that given a finite automaton A with states Q and input set I, output alphabet U, then one can expand the states to Q' such that the new automaton A' embeds into a cascade of "simple", irreducible automata: In particular, A is emulated by a feed-forward cascade of (1) automata whose transformation semigroups are finite simple groups and (2) automata that are banks of flip-flops running in parallel.[nb 1] The new automaton A' has the same input and output symbols as A. Here, both the states and inputs of the cascaded automata have a very special hierarchical coordinate form.

Moreover, each simple group (prime) or non-group irreducible semigroup (subsemigroup of the flip-flop monoid) that divides the transformation semigroup of A must divide the transformation semigroup of some component of the cascade, and only the primes that must occur as divisors of the components are those that divide A's transformation semigroup.

Group complexity

The Krohn–Rhodes complexity (also called group complexity or just complexity) of a finite semigroup S is the least number of groups in a wreath product of finite groups and finite aperiodic semigroups of which S is a divisor.

All finite aperiodic semigroups have complexity 0, while non-trivial finite groups have complexity 1. In fact, there are semigroups of every non-negative integer complexity. For example, for any n greater than 1, the multiplicative semigroup of all (n+1) × (n+1) upper-triangular matrices over any fixed finite field has complexity n (Kambites, 2007).

A major open problem in finite semigroup theory is the decidability of complexity: is there an algorithm that will compute the Krohn–Rhodes complexity of a finite semigroup, given its multiplication table? Upper bounds and ever more precise lower bounds on complexity have been obtained (see, e.g. Rhodes & Steinberg, 2009). Rhodes has conjectured that the problem is decidable.[2]

History and applications

At a conference in 1962, Kenneth Krohn and John Rhodes announced a method for decomposing a (deterministic) finite automaton into "simple" components that are themselves finite automata. This joint work, which has implications for philosophy[citation needed], comprised both Krohn's doctoral thesis at Harvard University and Rhodes' doctoral thesis at MIT.[3] Simpler proofs, and generalizations of the theorem to infinite structures, have been published since then (see Chapter 4 of Rhodes and Steinberg's 2009 book The q-Theory of Finite Semigroups for an overview).

In the 1965 paper by Krohn and Rhodes, the proof of the theorem on the decomposition of finite automata (or, equivalently sequential machines) made extensive use of the algebraic semigroup structure. Later proofs contained major simplifications using finite wreath products of finite transformation semigroups. The theorem generalizes the Jordan–Hölder decomposition for finite groups (in which the primes are the finite simple groups), to all finite transformation semigroups (for which the primes are again the finite simple groups plus all subsemigroups of the "flip-flop" (see above)). Both the group and more general finite automata decomposition require expanding the state-set of the general, but allow for the same number of input symbols. In the general case, these are embedded in a larger structure with a hierarchical "coordinate system".

One must be careful in understanding the notion of "prime" as Krohn and Rhodes explicitly refer to their theorem as a "prime decomposition theorem" for automata. The components in the decomposition, however, are not prime automata (with prime defined in a naïve way); rather, the notion of prime is more sophisticated and algebraic: the semigroups and groups associated to the constituent automata of the decomposition are prime (or irreducible) in a strict and natural algebraic sense with respect to the wreath product (Eilenberg, 1976). Also, unlike earlier decomposition theorems, the Krohn–Rhodes decompositions usually require expansion of the state-set, so that the expanded automaton covers (emulates) the one being decomposed. These facts have made the theorem difficult to understand and challenging to apply in a practical way—until recently, when computational implementations became available (Egri-Nagy & Nehaniv 2005, 2008).

H.P. Zeiger (1967) proved an important variant called the holonomy decomposition (Eilenberg 1976).[nb 2] The holonomy method appears to be relatively efficient and has been implemented computationally by A. Egri-Nagy (Egri-Nagy & Nehaniv 2005).

Meyer and Thompson (1969) give a version of Krohn–Rhodes decomposition for finite automata that is equivalent to the decomposition previously developed by Hartmanis and Stearns, but for useful decompositions, the notion of expanding the state-set of the original automaton is essential (for the non-permutation automata case).

Many proofs and constructions now exist of Krohn–Rhodes decompositions (e.g., [Krohn, Rhodes & Tilson 1968], [Ésik 2000], [Diekert et al. 2012]), with the holonomy method the most popular and efficient in general (although not in all cases). Owing to the close relation between monoids and categories, a version of the Krohn–Rhodes theorem is applicable to category theory. This observation and a proof of an analogous result were offered by Wells (1980).[nb 3]

The Krohn–Rhodes theorem for semigroups/monoids is an analogue of the Jordan–Hölder theorem for finite groups (for semigroups/monoids rather than groups). As such, the theorem is a deep and important result in semigroup/monoid theory. The theorem was also surprising to many mathematicians and computer scientists[nb 4] since it had previously been widely believed that the semigroup/monoid axioms were too weak to admit a structure theorem of any strength, and prior work (Hartmanis & Stearns) was only able to show much more rigid and less general decomposition results for finite automata.

Work by Egri-Nagy and Nehaniv (2005, 2008–) continues to further automate the holonomy version of the Krohn–Rhodes decomposition extended with the related decomposition for finite groups (so-called Frobenius–Lagrange coordinates) using the computer algebra system GAP.

Applications outside of the semigroup and monoid theories are now computationally feasible. They include computations in biology and biochemical systems (e.g. Egri-Nagy & Nehaniv 2008), artificial intelligence, finite-state physics, psychology, and game theory (see, for example, Rhodes 2009).

See also

Notes

  1. ^ Holcombe (1982) pp. 141–142
  2. ^ J. Rhodes, Keynote talk at the International Conference on Semigroups & Algebraic Engineering (Aizu, Japan), 26 March 1997.
  3. ^ 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.

  1. ^ The flip-flop is the two-state automaton with three input operations: the identity (which leaves its state unchanged) and the two reset operations (which overwrite the current state by a resetting to a particular one of the two states). This can be considered a one-bit read-write storage unit: the identity corresponds to reading the bit (while leaving its value unaltered), and the two resets to setting the value of the bit to 0 or 1. Note that a reset is an irreversible operator as it destroys the currently stored bit value. NB: The semigroup of the flip-flop and all its subsemigroups are irreducible.
  2. ^ Eilenberg 1976, as well as Dömösi and Nehaniv, 2005, present proofs that correct an error in Zeiger's paper.
  3. ^ See also (Tilson 1989)
  4. ^ C.L. Nehaniv, Preface to (Rhodes, 2009)

References

Further reading

Read other articles:

Sup kerang Sup miso kerang hitam di sebuah restoran di Tokyo Sup kerang adalah sup yang dibuat dengan menggunakan kerang sebagai bahan utamanya. Sup kerang dapat disiapkan sebagai sup tipis berbahan dasar kaldu atau krim/susu dan sebagai sup kental bergaya sup krim. Di Jepang, sup miso panas yang dimasak dengan kerang dipercaya oleh beberapa orang sebagai obat pengar. Gambaran Sup kerang dibuat dengan menggunakan kerang sebagai bahan utamanya. Bahan tambahan dapat mencakup wortel, seledri, ba...

 

American horror media franchise The ExorcistOfficial franchise logoCreated byWilliam Peter BlattyOriginal workThe Exorcist (1971)OwnerHoya Productions (1973) Warner Bros. (1973–1977; 1991–2005) 20th Century Fox (1990; 2016–2017) Universal Pictures (with Blumhouse; 2023–present) Morgan Creek (1988–present)Print publicationsNovel(s)The Exorcist (1971)Legion (1983)Exorcist: The Beginning (2004)Films and televisionFilm(s)The Exorcist (1973) Exorcist II: The Heretic (1977) The Exorcist I...

 

Jack and JillPoster rilis teatrikalSutradaraDennis DuganProduserAdam SandlerJack GiarraputoTodd GarnerSkenarioAdam SandlerSteve KorenCeritaBen ZookPemeranAdam SandlerAl PacinoKatie HolmesPenata musikRupert Gregson-WilliamsWaddy WachtelSinematograferDean CundeyPenyuntingTom CostainPerusahaanproduksiHappy Madison ProductionsDistributorColumbia PicturesTanggal rilis 11 November 2011 (2011-11-11) Durasi91 menit[1]NegaraAmerika SerikatBahasaInggrisAnggaran$79 juta[2]Pend...

Poster The Art Workers Coalition And Babies, yang menghubungkan pembantaian My Lai dengan sentimen anti-perang, adalah singkatnya poster paling sukses menentang Perang Vietnam.[1] And babies (26 Desember 1969[2]) adalah sebuah poster anti-Perang Vietnam.[1] Ini adalah contoh terkenal dari seni propaganda[3] dari konflik Vietnam yang memakai foto berwarna dari Pembantaian My Lai yang diambil oleh fotografer AS Ronald L. Haeberle pada 16 Maret 1968. Foto tersebut...

 

Совреме́нные ми́фы — культурные явления, обладающие мифологической природой, но зародившиеся и существующие в культуре научно-рационального общества[1]. Явление современного мифа соотносится с процессами ремифологизации как стратегией толкования мифа, как зна�...

 

Burj Khalifaبرج خليفةcode: ar is deprecated Burj KhalifaRekor tinggiTertinggi di dunia sejak 2009[I]DidahuluiTaipei 101Informasi umumStatusCompletedJenisPenggunaan campuranGaya arsitekturNeo-futurismeLokasiDubaiAlamat1 Sheikh Mohammed bin Rashid BoulevardNegaraUni Emirat ArabDinamai berdasarkanSheikh KhalifaMulai dibangun6 Januari 2004 (2004-01-06)Pengatapan17 January 2009Rampung1 Oktober 2009 (2009-10-1)Dibuka4 January 2010BiayaUS$1.5 billionPemilikEmaar PropertiesTinggiArs...

Baridinae Ceutorhynchus americanus à Nashville, dans le TennesseeClassification Règne Animalia Embranchement Arthropoda Classe Insecta Ordre Coleoptera Famille Curculionidae Sous-familleBaridinaeSchoenherr[1], 1836 Synonymes Conoderinae Schönherr, 1833 Orobitidinae C.G. Thomson, 1859 Les Baridinae sont une sous-famille d'insectes coléoptères de la famille des Curculionidae. Liste des tribus Groupe de tribus Baridinae: Ambatini - Anopsilini - Baridini - Madarini - Mad...

 

Un homme urinant dans un urinoir. La miction (du latin mingere, « uriner »), l'action d'uriner, désigne l'élimination d'urine par la vidange de la vessie. Description Loup gris urinant pour marquer son territoire. Les observations des mictions de mammifères d'une équipe du Georgia Institute of Technology ont mis en évidence en 2013 une loi expérimentale : la majorité des mammifères, quelle que soit leur taille et leur masse[1], mettent approximativement 21 secondes po...

 

Penaklukan Suriah oleh MuslimBagian dari Penaklukan Islam dan Peperangan Romawi Timur-ArabPeta penaklukan Khalid bin Walid di SuriahTanggal634-638LokasiPalestina, Suriah, Yordania, Lebanon, Israel dan Anatolia TenggaraHasil Kemenangan RasyidinPerubahanwilayah Levant dikuasai oleh MuslimPihak terlibat Kekaisaran BizantiumKerajaan Ghassaniyah Kekhalifahan RasyidinTokoh dan pemimpin Heraklius Jabalah bin al-Aiham Theodore Trithyrius Vahan Vardan Thomas Buccinator Gregory Abu Bakar Ash-Shiddiq Um...

Eumalacostraca Atlantic blue crabs, Callinectes sapidus Klasifikasi ilmiah Kerajaan: Animalia Filum: Arthropoda Subfilum: Crustacea Kelas: Malacostraca Subkelas: EumalacostracaGrobben, 1892 Superordo Syncarida Peracarida Eucarida Eumalacostraca adalah subkelas dari krustasea, yang mengandung hampir semua malacostraca hidup, atau sekitar 40.000 spesies dijelaskan.[1] Subkelas lainnya adalah Phyllocarida dan mungkin Hoplocarida.[2] Eumalacostraca memiliki 19 segmen (5 cephalic,...

 

For the journals, see Ostraka (journal). For the similarly pronounced city on the Volga River near the Caspian Sea, see Astrakhan. Broken piece of pottery with inscription Ostrakon inscribed with Kimon [son] of Miltiades, for Cimon, an Athenian statesman. Ostrakon of Megacles, son of Hippocrates (inscription: ΜΕΓΑΚΛΕΣ ΗΙΠΠΟΚΡΑΤΟΣ), 487 BC. On display in the Ancient Agora Museum in Athens, housed in the Stoa of Attalus Ancient Greek ostraca voting for the ostracization of Th...

 

Abubakar bin AliNamaAbubakar bin AliKebangsaanIndonesia, Alawiyyin, Arab-Indonesia Habib Abubakar bin Ali Shahab (28 Rajab 1287 H (24 October 1870) - 18 Maret 1944) adalah tokoh keturunan Arab-Indonesia, yang aktif dalam pergerakan dan pendidikan Islam pada masa pra-kemerdekaan Indonesia, serta merupakan pendiri Jamiat Kheir dan Malja Al Shahab. Masa muda dan pendidikan Lahir di Jakarta pada tanggal 28 Rajab 1288 H, dari seorang ayah bernama Ali bin Abubakar bin Umar Shahab, kelahiran Damun, ...

Vecchia locomotiva a vapore Il trasporto ferroviario è lo spostamento di persone e/o cose da un luogo ad un altro per mezzo di un sistema specializzato comunemente chiamato ferrovia, utilizzando un mezzo di trasporto a trazione ferroviaria denominato treno. Mappa della rete ferroviaria mondiale Indice 1 Tipologia 2 Aspetti energetici e ambientali 3 Aspetti economici 4 Sicurezza 5 Diritto comunitario 6 Note 7 Bibliografia 8 Voci correlate 9 Altri progetti 10 Collegamenti esterni Tipologia Sta...

 

Land warfare branch of Germany's military For the World War I army, see Imperial German Army. For the World War II army, see German Army (1935–1945). For other uses, see German Army (disambiguation). German ArmyHeerLogo of the German ArmyFounded11 November 1955 (11 November 1955)Country GermanyTypeLand forceSize62,800 (2023)Part ofBundeswehrArmy CommandStrausbergMotto(s)Schützen, helfen, vermitteln, kämpfen('Protect, help, moderate, fight')Anniversaries12 November 1955Equip...

 

Questa voce sull'argomento giochi olimpici è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Jugoslavia ai Giochi della IX OlimpiadeAmsterdam 1928 Codice CIOYUG Comitato nazionaleJugoslovenski olimpijski komitet Atleti partecipanti34 in 6 discipline Di cui uomini/donne34 - 0 PortabandieraDimitrije Stefanović Medagliere Posizione 21ª 1 1 3 5 Cronologia olimpica (sommario)Giochi olimpici e...

زهير فضال معلومات شخصية الاسم الكامل زهير فضال الميلاد 23 ديسمبر 1989 (العمر 34 سنة)تطوان  الطول 191 سنتيمتر  مركز اللعب مدافع الجنسية المغرب إسبانيا (يناير 2012–)  معلومات النادي النادي الحالي ريال بلد الوليد الرقم 3 مسيرة الشباب سنوات فريق المغرب التطواني Vilamalla CF Peralada [...

 

For the establishment in Southport, see Smedley Hydro. County building in Matlock, Derbyshire, England County Hall, MatlockCounty Hall, MatlockLocationMatlock, DerbyshireCoordinates53°08′32″N 1°33′05″W / 53.1422°N 1.5514°W / 53.1422; -1.5514Built1867Architectural style(s)Victorian style Listed Building – Grade IIDesignated26 October 1972Reference no.1248195 Location of County Hall, Matlock in Derbyshire The County Hall is a municipal building in Matl...

 

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Chairman of the Federation Council Russia – news · newspapers · books · scholar · JSTOR (May 2019) (Learn how and when to remove this message) Chairman of the Federation Council of the Federal Assembly of the Russian FederationПредседатель Со...

Head of an Eastern Orthodox or Eastern Catholic monastery Not to be confused with Hegemon.Ihumen redirects here. For the modern village of that former name, see Chervyen.This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Hegumen – news · newspapers · books · scholar · JSTOR (December 2016) Hegumen, he...

 

This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (February 2019) (Learn how and when to remove this message) David E. McGiffertAssistant Secretary of Defense for International Security AffairsIn officeApril 4, 1977 – January 20, 1981PresidentJimmy CarterPreceded byEugene V. McAuliffeSucceeded byBing WestUnited State...