Теория Крона – Родса

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

Крон и Родс нашли общее разложение для конечных автоматов . Авторы обнаружили и доказали неожиданный крупный результат в теории конечных полугрупп, раскрывающий глубокую связь между конечными автоматами и полугруппами.

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

Пусть T — полугруппа. Полугруппа , S являющаяся гомоморфным образом подполугруппы группы T называется дивизором группы T. ,

Теорема Крона-Роудса для конечных полугрупп , что каждая конечная полугруппа S является дивизором конечного знакопеременного сплетения конечных утверждает простых групп , каждая из которых является дивизором S , и конечных апериодических полугрупп (которые не содержат нетривиальных подгрупп ).

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

Более того, каждая простая группа ( простое число ) или негрупповая неприводимая полугруппа (подполугруппа моноида триггера ), которая делит полугруппу преобразований A, должна разделять полугруппу преобразований некоторого компонента каскада, и только те простые числа, которые должны встречаться как делителями компонентов являются те, которые делят A. полугруппу преобразований

Групповая сложность

Сложность Крона –Роудса (также называемая групповой сложностью или просто сложностью ) конечной полугруппы S — это наименьшее количество групп в сплетении которых является S. конечных групп и конечных апериодических полугрупп , дивизором

Все конечные апериодические полугруппы имеют сложность 0, а нетривиальные конечные группы имеют сложность 1. Фактически существуют полугруппы любой неотрицательной целочисленной сложности. Например, для любого n больше 1 мультипликативная полугруппа всех ( n +1) × ( n +1) верхнетреугольных матриц над любым фиксированным конечным полем имеет сложность n (Kambites, 2007).

Основной открытой проблемой в теории конечных полугрупп является разрешимость сложности : существует ли алгоритм , который вычислит сложность Крона–Родса конечной полугруппы по ее таблице умножения ? Были получены верхние оценки и все более точные нижние оценки сложности (см., например, Rhodes & Steinberg, 2009). Родс предположил, что проблема разрешима.

История и приложения

На конференции 1962 года Кеннет Крон и Джон Роудс объявили о методе разложения (детерминированного) конечного автомата на «простые» компоненты, которые сами являются конечными автоматами. Эта совместная работа, имеющая значение для философии , включала в себя как докторскую диссертацию Крона в Гарвардском университете , так и докторскую диссертацию Родса в Массачусетском технологическом институте . С тех пор были опубликованы более простые доказательства и обобщения теоремы на бесконечные структуры ( см. в главе 4 книги Родса и Стейнберга 2009 года «q-теория конечных полугрупп обзор »).

В статье Крона и Роудса 1965 года доказательство теоремы о разложении конечных автоматов (или, что то же самое, последовательных машин ) широко использовало структуру алгебраической полугруппы . Более поздние доказательства содержали серьезные упрощения с использованием конечных сплетений конечных полугрупп преобразований. Теорема обобщает разложение Йордана – Гельдера для конечных групп (в которых простые числа являются конечными простыми группами) на все конечные полугруппы преобразований (для которых простые числа снова являются конечными простыми группами плюс все подполугруппы «триггера» ( смотри выше)). И групповая, и более общая декомпозиция конечных автоматов требуют расширения набора состояний общего, но допускают одинаковое количество входных символов. В общем случае они встроены в более крупную структуру с иерархической «системой координат».

Следует быть осторожным в понимании понятия «простое число», поскольку Крон и Родс явно называют свою теорему «теоремой простого разложения» для автоматов. Однако компоненты разложения не являются простыми автоматами (с простым определением простых чисел); скорее, понятие простого числа является более сложным и алгебраическим: полугруппы и группы, связанные с составляющими автоматами разложения, являются простыми (или неприводимыми) в строгом и естественном алгебраическом смысле относительно сплетения ( Eilenberg , 1976). Кроме того, в отличие от более ранних теорем о разложении, разложения Крона – Родса обычно требуют расширения набора состояний, так что расширенный автомат покрывает (эмулирует) разлагаемый автомат. Эти факты затрудняли понимание теоремы и ее практическое применение — до недавнего времени, когда стали доступны вычислительные реализации (Egri-Nagy & Nehaniv 2005, 2008).

HP Zeiger (1967) доказал важный вариант, названный разложением голономии (Eilenberg 1976). Метод голономии оказался относительно эффективным и был реализован вычислительно А. Эгри-Надь (Эгри-Надь и Неханив, 2005).

Мейер и Томпсон (1969) предлагают версию разложения Крона–Роудса для конечных автоматов, которая эквивалентна разложению, ранее разработанному Хартманисом и Стернсом, но для полезных разложений важно понятие расширения набора состояний исходного автомата ( для случая неперестановочных автоматов).

В настоящее время существует множество доказательств и конструкций разложений Крона–Роудса (например, [Krohn, Rhodes & Tilson 1968], [Ésik 2000], [Diekert et al. 2012]), причем метод голономии в целом является наиболее популярным и эффективным (хотя не во всех случаях). Из-за тесной связи между моноидами и категориями версия теоремы Крона-Родса применима к теории категорий . Это наблюдение и доказательство аналогичного результата были предложены Уэллсом (1980).

Теорема Крона–Родса для полугрупп/моноидов является аналогом теоремы Йордана–Гёльдера для конечных групп (для полугрупп/моноидов, а не групп). По существу, эта теорема представляет собой глубокий и важный результат в теории полугрупп/моноидов. Теорема также удивила многих математиков и компьютерщиков. поскольку ранее широко считалось, что аксиомы полугруппы/моноида слишком слабы, чтобы допускать структурную теорему какой-либо силы, а предыдущая работа (Хартманис и Стернс) смогла показать только гораздо более жесткие и менее общие результаты декомпозиции для конечных автоматов.

Работа Эгри-Надя и Неханива (2005, 2008–) продолжает дальнейшую автоматизацию голономной версии разложения Крона–Роудса, расширенной за счет соответствующего разложения для конечных групп (так называемых координат Фробениуса–Лагранжа ) с использованием системы компьютерной алгебры GAP .

Приложения за пределами теорий полугрупп и моноидов теперь вычислительно осуществимы. Они включают вычисления в биологии и биохимических системах (например, Egri-Nagy & Nehaniv 2008), искусственном интеллекте конечных состояний , физике , психологии и теории игр (см., например, Rhodes 2009).

См. также

• Полугрупповое действие
• Полугруппа трансформации
• Отношения Грина

---

Ссылки

• Баррингтон, Дэвид А. Микс (1992). «Некоторые задачи, связанные с полиномами Разборова-Смоленского». В Патерсоне, М.С. (ред.). Сложность булевой функции, Sel. Пап. Симп., Дарем/Великобритания, 1990 г. Серия конспектов лекций Лондонского математического общества. Том. 169. стр. 109–128. ISBN  978-0-521-40826-4 . Збл   0769.68041 .
• Дикерт, Волкер; Крейсер, Манфред; Стейнберг, Бенджамин (2012). «Теорема Крона-Родса и локальные делители» Основы компьютера . 116 (1–4): 65–77. arXiv : 1111.1585 . дои : 10.3233/FI-2012-669 . ISSN   0169-2968 .
• Пал Домёси; Кристофер Л. Неханив (2005). Алгебраическая теория автоматных сетей: Введение . Монографии SIAM по дискретной математике и приложениям. Общество промышленной и прикладной математики. ISBN  978-0-89871-569-9 .
• Эгри-Надь, А.; и Неханив, CL (2005), «Алгебраическая иерархическая декомпозиция автоматов с конечным состоянием: сравнение реализаций теории Крона – Родса», на 9-й Международной конференции по внедрению и применению автоматов (CIAA 2004), Кингстон, Канада, 22–24 июля. , 2004, Переработанные избранные статьи , Редакторы: Домарацкий, М.; Охотин А.; Саломаа, К.; и др. ; Конспекты лекций Springer по информатике , Vol. 3317, стр. 315–316, 2005 г.
• Эгри-Надь, Аттила; Неханив, Кристофер Л. (лето 2008 г.). «Иерархические системы координат для понимания сложности и ее эволюции с применением к генетическим регуляторным сетям» (PDF) . Искусственная жизнь . 14 (3): 299–312. дои : 10.1162/артл.2008.14.3.14305 . hdl : 2299/16600 . ISSN   1064-5462 . ПМИД   18489252 .
• Эйленберг, Сэмюэл (1976). Автоматы, языки и машины . Чистая и прикладная математика, Конспекты лекций по математике. Нью-Йорк: Академическая пресса. ISBN  978-0-12-234001-7 . Две главы написаны Бретом Тилсоном.
• Есик, З. (март 2000 г.). «Доказательство теоремы о разложении Крона – Родса». Теоретическая информатика . 234 (1–2): 287–300. дои : 10.1016/s0304-3975(99)00315-1 . ISSN   0304-3975 .
• Хартманис, Юрис ; Стернс, RE (1966). Алгебраическая структурная теория последовательных машин . Прентис-Холл. АСИН   B0006BNWTE .
• Холкомб, WML (1982). Алгебраическая теория автоматов . Кембриджские исследования по высшей математике. Том. 1. Издательство Кембриджского университета . ISBN  978-0-521-60492-5 . Збл   0489.68046 .
• Камбитс, Марк (2007). «О сложности Крона–Родоса полугрупп верхнетреугольных матриц». Международный журнал алгебры и вычислений . 17 (1): 187–201. CiteSeerX   10.1.1.657.4000 . дои : 10.1142/S0218196707003548 . ISSN   0218-1967 .
• Крон, КР; и Роудс, Дж. Л. (1962), «Алгебраическая теория машин», Труды симпозиума по математической теории автоматов (редактор: Фокс, Дж.), ( Wiley – Interscience )
• Крон, Кеннет; Роудс, Джон (апрель 1965 г.). «Алгебраическая теория машин. I. Теорема о простом разложении для конечных полугрупп и машин» (PDF) . Труды Американского математического общества . 116 : 450–464. дои : 10.2307/1994127 . ISSN   0002-9947 . JSTOR   1994127 . Проверено 18 сентября 2010 г.
• Крон, Кеннет; Роудс, Джон Л. (август 1968 г.). Арбиб, Майкл А. (ред.). Алгебраическая теория машин, языков и полугрупп . Академическая пресса. ISBN  978-0-12-059050-6 .
• Лаллемент, Жерар (1 марта 1971 г.). «О простой теореме разложения конечных моноидов». Теория вычислительных систем . 5 (1): 8–12. дои : 10.1007/BF01691462 . ISSN   1433-0490 .
• Мейер, Арканзас; Томпсон, К. (1 июня 1969 г.). «Замечания об алгебраической декомпозиции автоматов» (PDF) . Теория вычислительных систем . 3 (2): 110–118. CiteSeerX   10.1.1.649.4716 . дои : 10.1007/BF01746516 . ISSN   1432-4350 .
• Джон Роудс; Бенджамин Стейнберг (17 декабря 2008 г.). q-теория конечных полугрупп . Спрингер Верлаг. ISBN  978-0-387-09780-0 .
• Штраубинг, Ховард; Териен, Денис (2002). «Слабо итерированные блочные произведения конечных моноидов» . В Райсбауме, Серджио (ред.). Конспекты лекций по информатике . ЛАТИНСКИЙ 2002: Теоретическая информатика. Том. 2286. Берлин: Шпрингер. стр. 91–104. дои : 10.1007/3-540-45995-2_13 . ISBN  978-3-540-43400-9 . Проверено 18 сентября 2010 г.
• Роудс, Джон Л. (3 сентября 2009 г.). Неханив, Кристофер Л. (ред.). Приложения теории автоматов и алгебры через математическую теорию сложности к физике конечных состояний, биологии, философии и играм . Сингапур: Всемирная научная издательская компания. ISBN  978-981-283-696-0 .
• Тилсон, Брет (сентябрь 1987 г.). «Категории как алгебра: существенный ингредиент теории моноидов» . Журнал чистой и прикладной алгебры . 48 (1–2): 83–198. дои : 10.1016/0022-4049(87)90108-3 . ISSN   0022-4049 .
• Уэллс, К. (1980). «Теорема Крона – Родса для категорий» . Журнал алгебры . 64 : 37–45. дои : 10.1016/0021-8693(80)90130-1 . ISSN   0021-8693 .
• Зейгер, HP (апрель 1967 г.). «Каскадный синтез конечных автоматов». Информация и контроль . 10 (4): 419–433. дои : 10.1016/S0019-9958(67)90228-8 . ISSN   1462-3889 . Опечатка: Информация и контроль 11 (4): 471 (1967), плюс опечатка.

Дальнейшее чтение

• Роудс, Джон Л. (2010). Кристофер Л. Неханив (ред.). Приложения теории автоматов и алгебры: через математическую теорию сложности к биологии, физике, психологии, философии и играм . World Scientific Pub Co Inc. ISBN  978-981-283-696-0 .
• Роудс, Джон ; Стейнберг, Бенджамин (17 декабря 2008 г.). q-теория конечных полугрупп . Спрингер Верлаг. ISBN  978-0-387-09780-0 .
• Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схемы . Прогресс в теоретической информатике. Базель: Биркхойзер. ISBN  978-3-7643-3719-3 . Заказ №   0816.68086 .

Внешние ссылки

• Веб-страница профессора Джона Л. Роудса, Калифорнийский университет в Беркли
• SgpDec: Иерархическая композиция и декомпозиция групп перестановок и полугрупп преобразований , разработанная А. Эгри-Надь и К. Л. Неханивом . Пакет программного обеспечения с открытым исходным кодом для системы компьютерной алгебры GAP .
• Джон Л. Роудс (2010). Кристофер Л. Неханив (ред.). Приложения теории автоматов и алгебры: через математическую теорию сложности к биологии, физике, психологии, философии и играм . World Scientific Pub Co Inc. ISBN  978-981-283-696-0 .
• Введение в теорему Крона-Родса (раздел 5); часть MOOC «Введение в перенормировку» Института Санта-Фе , написанного Саймоном ДеДео.