Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математика мен информатикада Кроун-Родос теориясы (немесе алгебралық автоматтар теориясы) – шекті жартылай топтар мен автоматтарды зерттеуге бағытталған, оларды элементар компоненттерге жіктеуді көздейтін тәсіл. Бұл компоненттер шекті апериодты жартылай топтарға және кері байланыссыз (осыған "тоқу өнімі" немесе "каскад" деп аталады) біріктірілген шекті қарапайым топтарға сәйкес келеді. Крон мен Родс шекті автоматтар үшін жалпы жіктеуді тапты. Авторлар шекті жартылай топтар теориясында күтпеген маңызды нәтижелерді ашты және дәлелдеді, бұл шекті автоматтар мен жартылай топтар арасындағы терең байланысты аңғарды.
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.
Кроун-Родос теоремасының анықтамасы мен сипаттамасы
T жартылай топ болсын. T-нің субсемигрупасының гомоморфты бейнесі болып табылатын S жартылай тобы T-нің бөлгіші деп аталады.
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.
Шекті жартылай топтар үшін Крохн–Родс теоремасы, әрбір шекті S жартылай тобы, S-нің бөлгіші болып табылатын шекті қарапайым топтардың шекті ауыспалы тоқу өнімінің бөлгіші болып табылады, сондай-ақ шекті апериодты жартылай топтардың (тривиалды емес субтоптары жоқ) бөлгіші болып табылады. Автоматтар түріндегі шекті автоматтар үшін Крохн–Родс теоремасы, Q күйлері мен I кіріс жиыны бар шекті автомат A берілгенде, Q' күйлерін кеңейтуге болады, содан кейін жаңа автомат A', "қарапайым", азайтылмайтын автоматтардың каскадына енуі мүмкін: Атап айтқанда, A, (1) трансформациялық жартылай топтары шекті қарапайым топтар болатын автоматтардың тізбегімен және (2) параллель жұмыс істейтін флип-флоптар банктері болатын автоматтармен эмуляцияланады. Жаңа автомат A', A-мен бірдей кіріс және шығыс символдарына ие. Мұнда, каскадталған автоматтардың күйлері мен кірістері ерекше иерархиялық координаттық формаға ие. Сонымен қатар, A-ның трансформациялық жартылай тобын бөлетін әрбір қарапайым топ (прим) немесе топқа жатпайтын азайтылмайтын жартылай топ (флип-флоп моноидінің субсемигрупасы) каскадтың кейбір компоненттерінің трансформациялық жартылай тобын бөлуі керек, және компоненттердің бөлгіштері ретінде пайда болуы тиіс жай сандар ғана A-ның трансформациялық жартылай тобын бөлуі керек.
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). 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. 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.
Тарих және қолдану
1962 жылы Кеннет Кроун мен Джон Родс конференцияда (детерминистік) шекті автоматты "қарапайым" компоненттерге бөлшектеу әдісін жариялады, бұл компоненттердің өзі шекті автоматтар болып табылады. Философияға қатысы бар осы бірлескен жұмыс Кроунның Гарвард университетіндегі докторлық диссертациясы және Родстың МТИ-дегі докторлық диссертациясын құрады. Содан бері теореманың оңайрақ дәлелдемелері мен шексіз құрылымдарға жалпыламалары жарияланды (толық мәліметтер үшін Родс пен Штайнбергтің 2009 жылғы «The q Theory of Finite Semigroups» кітабының 4-тарауын қараңыз). Кроун мен Родстың 1965 жылғы мақаласында шекті автоматтардың (немесе, балама ретінде, тізбекті машиналардың) бөлшектелу теоремасының дәлелі алгебралық жартылай топ құрылымын кеңінен пайдаланды. Кейінгі дәлелдемелерде шекті түрлендіру жартылай топтарының шекті толық өнімдерін қолдану арқылы маңызды жеңілдетулер енгізілді. Теорема шекті топтар үшін Джордан-Хёльдер бөлшектелуін (онда алғашқы сандар шекті қарапайым топтар болып табылады) барлық шекті түрлендіру жартылай топтарына (онда алғашқы сандар тағы да шекті қарапайым топтар және «қосқыш» жартылай топтарының барлығы) жалпылайды (жоғарыда қараңыз). Топтық және жалпы шекті автоматтардың бөлшектелуі үшін жалпы жағдайдың күйлер жиынтығын кеңейту қажет, бірақ кіріс символдарының саны сол күйінде қалады. Жалпы жағдайда, олар иерархиялық «координаталық жүйемен» жабдықталған үлкен құрылымға енгізіледі. «Алғашқы» ұғымын түсінуде сақтық таныту қажет, өйткені Кроун мен Родс өз теоремаларын автоматтар үшін «алғашқы бөлшектелу теоремасы» деп атайды. Дегенмен, бөлшектелудегі компоненттер алғашқы автоматтар емес (наивті түрде анықталған алғашқымен); керісінше, «алғашқы» ұғымы күрделірек және алгебралық: бөлшектелудің құрамдас автоматтарына байланысты жартылай топтар мен топтар толық өнімге қатысты қатаң және табиғи алгебралық мағынада алғашқы (немесе толыққанды емес) болып табылады (Эйленберг, 1976). Бұрынғы бөлшектелу теоремаларынан айырмашылығы, Кроун-Родс бөлшектелулері көбінесе күйлер жиынтығын кеңейтуді қажет етеді, сондықтан кеңейтілген автомат бөлшектелетін автоматты қамтиды (эмуляциялайды). Осы фактілер теореманы түсінуді қиындатты және оны практикалық тұрғыда қолдануды қиын етті – соңғы кезде есептеулік іске асырулар қолжетімді болғанға дейін (Егри Наги & Неханив 2005, 2008). Х. П. Зейгер (1967) голономиялық бөлшектелу деп аталатын маңызды нұсқаны дәлелдеді (Эйленберг 1976). Голономия әдісі салыстырмалы түрде тиімді болып көрінеді және А. Эгри Наги есептеу арқылы іске асырды (Egri Nagy & Nehaniv 2005). Мейер мен Томпсон (1969) шекті автоматтар үшін Кроун-Родс бөлшектелуін береді, ол бұрын Хартманис пен Стернс жасаған бөлшектелумен тең, бірақ пайдалы бөлшектелулер үшін бастапқы автоматтың күйлер жиынтығын кеңейту ұғымы маңызды (пермутациясыз автоматтар үшін). Қазір Кроун-Родс бөлшектелулерінің көптеген дәлелдемелері мен құрылымдары бар (мысалы, [Krohn, Rhodes & Tilson 1968], [Ésik 2000], [Diekert et al. 2012]), голономия әдісі жалпы алғанда ең танымал және тиімді (бірақ барлық жағдайларда емес). Моноидтар мен категориялар арасындағы тығыз байланыстың арқасында Кроун-Родс теоремасының нұсқасы категориялар теориясына қолданылады. Бұл байқауды және ұқсас нәтижеге дәлелдей отырып, Уэллс ұсынды (1980). Жартылай топтар/моноидтар үшін Кроун-Родс теоремасы шекті топтар үшін Джордан-Хёльдер теоремасының аналогы болып табылады (топтар емес, жартылай топтар/моноидтар үшін). Осылайша, теорема жартылай топтар/моноидтар теориясының терең және маңызды нәтижесі болып табылады. Теорема көптеген математиктер мен компьютерлік ғалымдарды таң қалдырды, өйткені бұрын жартылай топ/моноид аксиомалары кез-келген күшті құрылым теоремасын қабылдауға тым әлсіз деп саналған болатын, ал алдыңғы жұмыстар (Хартманис және Стернс) тек шекті автоматтар үшін әлдеқайда қатаң және жалпы бөлшектелу нәтижелерін көрсетуге ғана қол жеткізді. Эгри Наги мен Неханивтің (2005, 2008–) жұмыстары компьютерлік алгебра жүйесі GAP-ті қолдана отырып, шекті топтар үшін (Фробенус-Лагранж координаталары деп аталады) байланысты бөлшектелумен кеңейтілген Кроун-Родс бөлшектелуінің голономиялық нұсқасын одан әрі автоматтандыруды жалғастыруда. Жартылай топ және моноид теориясынан тыс қолданбалар қазір есептеу тұрғысынан мүмкін. Олар биология және биохимиялық жүйелердегі есептеулерді (мысалы, Эгри Наги мен Неханив 2008), жасанды интеллект, шекті күй физикасы, психология және ойын теориясын қамтиды (мысалы, Родс 2009).
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, comprised both Krohn's doctoral thesis at Harvard University and Rhodes' doctoral thesis at MIT. 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). 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). 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 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).