Теория Крона — Роудса: Разложение конечных автоматов и полугрупп

Введение

В математике и информатике теория Крона — Родоса (или алгебраическая теория автоматов) — это подход к изучению конечных полугрупп и автоматов, направленный на их разложение на элементарные компоненты. Эти компоненты соответствуют конечным апериодическим полугруппам и конечным простым группам, которые объединяются без обратной связи (это объединение называется "венком произведений" или "каскадом"). Крон и Родос установили общее разложение для конечных автоматов. Авторы открыли и доказали неожиданный важный результат в теории конечных полугрупп, выявив глубокую связь между конечными автоматами и полугруппами.

Определения и описание теоремы Крона Родоса

Пусть T – полугруппа. Полугруппа S, являющаяся гомоморфным образом подполугруппы T, называется делителем T. Теорема Крона–Родса для конечных полугрупп утверждает, что каждая конечная полугруппа S является делителем конечного попеременного венка конечных простых групп, каждая из которых является делителем S, и конечных апериодических полугрупп (не содержащих нетривиальных подгрупп). В формулировке автоматов теорема Крона–Родса для конечных автоматов гласит, что для заданного конечного автомата A с множеством состояний Q и входным набором I, выходным алфавитом U, можно расширить множество состояний до Q' так, чтобы новый автомат A' встраивался в каскад "простых" и неприводимых автоматов: в частности, автомат A эмулируется каскадом последовательной подачи (1) автоматов, чьи полугруппы преобразований являются конечными простыми группами, и (2) автоматов, представляющих собой банки триггеров, работающих параллельно. Новый автомат A' имеет те же входные и выходные символы, что и A. Здесь как состояния, так и входы каскадных автоматов имеют особую иерархическую координатную форму. Более того, каждая простая группа (простое число) или негрупповая неприводимая полугруппа (подполугруппа моноида триггеров), делящая полугруппу преобразований A, должна делить полугруппу преобразований некоторого компонента каскада, и только те простые числа, которые должны встречаться в качестве делителей компонентов, делят полугруппу преобразований A'.

История и применение

На конференции в 1962 году Кеннет Крон и Джон Роудс объявили о методе разложения (детерминированного) конечного автомата на "простые" компоненты, которые сами являются конечными автоматами. Эта совместная работа, имеющая последствия для философии, включала как докторскую диссертацию Крона в Гарвардском университете, так и докторскую диссертацию Родса в MIT. С тех пор были опубликованы более простые доказательства и обобщения теоремы для бесконечных структур (см. главу 4 книги Родса и Стейнберга 2009 года "Теория конечных полугрупп q" для обзора). В статье Крона и Родса 1965 года доказательство теоремы о разложении конечных автоматов (или, эквивалентно, последовательных машин) широко использовало алгебраическую структуру полугрупп. Последующие доказательства содержали существенные упрощения с использованием конечных венковых произведений конечных полугрупп преобразований. Теорема обобщает разложение Джордана — Хёльдера для конечных групп (в котором простыми являются конечные простые группы) на все конечные полугруппы преобразований (для которых простыми снова являются конечные простые группы плюс все подполугруппы "флип-флопа" (см. выше)). Как групповое, так и более общее разложение конечных автоматов требует расширения множества состояний общего автомата, но позволяет сохранить количество входных символов. В общем случае они встроены в более крупную структуру с иерархической "системой координат". Необходимо проявлять осторожность в понимании понятия "простой", поскольку Крон и Роудс явно называют свою теорему "теоремой о простом разложении" для автоматов. Компоненты в разложении, однако, не являются простыми автоматами (в наивном понимании этого термина); скорее, понятие простоты более сложное и алгебраическое: полугруппы и группы, связанные с составляющими автоматами разложения, являются простыми (или неразложимыми) в строгом и естественном алгебраическом смысле относительно венкового произведения (Eilenberg, 1976). Кроме того, в отличие от более ранних теорем разложения, разложения Крона — Родса обычно требуют расширения множества состояний, так что расширенный автомат покрывает (эмулирует) разлагаемый. Эти факты затрудняли понимание теоремы и ее практическое применение — до недавнего времени, когда стали доступны вычислительные реализации (Egri Nagy & Nehaniv 2005, 2008). Х. П. Зейгер (1967) доказал важный вариант, называемый голономическим разложением (Eilenberg 1976). Голономический метод представляется относительно эффективным и был реализован вычислительно А. Эгри Нагги (Egri Nagy & Nehaniv 2005). Майер и Томпсон (1969) приводят версию разложения Крона — Родса для конечных автоматов, эквивалентную разложению, ранее разработанному Хартманисом и Стернсом, но для полезных разложений необходимо расширение множества состояний исходного автомата (в случае непермутационных автоматов). В настоящее время существует множество доказательств и построений разложения Крона — Родса (например, [Krohn, Rhodes & Tilson 1968], [Ésik 2000], [Diekert et al. 2012]), причем голономический метод является наиболее популярным и эффективным в целом (хотя и не во всех случаях). Благодаря тесной связи между моноидами и категориями, версия теоремы Крона — Родса применима к теории категорий. Это наблюдение и доказательство аналогичного результата были предложены Уэллсом (1980). Теорема Крона — Родса для полугрупп/моноидов является аналогом теоремы Джордана — Хёльдера для конечных групп (для полугрупп/моноидов, а не групп). Таким образом, теорема представляет собой глубокий и важный результат в теории полугрупп/моноидов. Теорема также удивила многих математиков и специалистов в области компьютерных наук, поскольку ранее широко считалось, что аксиомы полугрупп/моноидов слишком слабы для теоремы о структуре какой-либо значимости, а предыдущие работы (Хартманиса и Стернса) могли показать лишь гораздо более жесткие и менее общие результаты разложения для конечных автоматов. Работы Эгри Наги и Неханива (2005, 2008–) продолжают автоматизировать голономическую версию разложения Крона — Родса, расширенную соответствующим разложением для конечных групп (так называемые координаты Фробениуса — Лагранжа) с использованием компьютерной алгебраической системы GAP. Приложения за пределами теорий полугрупп и моноидов теперь вычислительно осуществимы. Они включают вычисления в биологии и биохимических системах (например, Egri Nagy & Nehaniv 2008), искусственном интеллекте, физике конечных состояний, психологии и теории игр (см., например, Rhodes 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).