Теория Крона – Родса - Krohn–Rhodes theory
В математике и информатике , то теория Крон-Rhodes (или алгебраическая теория автоматов ) является подходом к изучению конечных полугрупп и автоматов , что стремится разложить их в терминах элементарных компонентов. Эти компоненты соответствуют конечным апериодическим полугруппам и конечным простым группам , которые комбинируются без обратной связи (это называется « сплетением » или «каскадом»).
Крон и Роудс нашли общее разложение для конечных автоматов . Однако в ходе своих исследований авторы обнаружили и доказали неожиданный важный результат в теории конечных полугрупп, выявив глубокую связь между конечными автоматами и полугруппами.
Определения и описание теоремы Крона – Родса.
Полугруппа S , которая является гомоморфным образ подполугруппы из Т называется быть делителем из T .
Теорема Крон-Rhodes для конечных полугрупп состояний , что любая конечная полугруппа 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 книги Steinberg и Родоса q- теории конечных полугрупп для обзора).
В статье Крона и Роудса 1965 г. в доказательстве теоремы о разложении конечных автоматов (или, что то же самое, последовательных машин ) широко использовалась структура алгебраической полугруппы . Более поздние доказательства содержали основные упрощения с использованием конечных сплетений конечных полугрупп преобразований. Теорема обобщает разложение Жордана – Гёльдера для конечных групп (в которых простые числа являются конечными простыми группами) на все конечные полугруппы преобразований (для которых простые числа снова являются конечными простыми группами плюс все подполугруппы «триггера» ( см. выше)). И групповая, и более общая декомпозиция конечных автоматов требует расширения набора состояний общего, но допускает то же количество входных символов. В общем случае они встроены в более крупную структуру с иерархической «системой координат».
Следует быть осторожным в понимании понятия «простое число», поскольку Крон и Роудс явно называют свою теорему «теоремой разложения на простые числа» для автоматов. Однако компоненты разложения не являются простыми автоматами (с простыми числами, определенными наивно); скорее, понятие простого числа является более сложным и алгебраическим: полугруппы и группы, связанные с составляющими автоматами разложения, являются простыми (или неприводимыми) в строгом и естественном алгебраическом смысле по отношению к сплетению (Eilenberg, 1976). Кроме того, в отличие от более ранних теорем о разложении, разложения Крона – Родса обычно требуют расширения набора состояний, так что расширенный автомат покрывает (имитирует) разлагаемый. Эти факты затрудняли понимание теоремы и затрудняли ее практическое применение - до недавнего времени, когда стали доступны вычислительные реализации (Egri-Nagy & Nehaniv 2005, 2008).
HP Zeiger (1967) доказал важный вариант, названный разложением голономии (Eilenberg 1976). Метод голономии оказался относительно эффективным и был реализован на вычислительной основе А. Эгри-Надь (Egri-Nagy & Nehaniv 2005).
Мейер и Томпсон (1969) дают версию разложения Крона – Родса для конечных автоматов, которая эквивалентна разложению, ранее разработанному Хартманисом и Стернсом, но для полезных разложений существенно важно понятие расширения множества состояний исходного автомата ( для случая неперестановочных автоматов).
Сейчас существует множество доказательств и конструкций разложений Крона – Родса (например, [Krohn, Rhodes & Tilson 1968], [Ésik 2000], [Diekert et al. 2012]), причем метод голономии в целом является наиболее популярным и эффективным (хотя не во всех случаях). Благодаря тесной связи между моноидами и категориями , версия теоремы Крона – Родса применима к теории категорий . Это наблюдение и доказательство аналогичного результата были предложены Уэллсом (1980).
Теорема Крона – Родса для полугрупп / моноидов является аналогом теоремы Жордана – Гёльдера для конечных групп (для полугрупп / моноидов, а не для групп). Таким образом, теорема является глубоким и важным результатом в теории полугрупп / моноидов. Эта теорема также вызвала удивление для многих математиков и компьютерных специалистов, поскольку ранее широко считалось, что аксиомы полугруппы / моноида слишком слабы, чтобы допустить какую-либо сильную структурную теорему, а предыдущие работы (Hartmanis & Stearns) могли лишь многое показать. более жесткие и менее общие результаты декомпозиции конечных автоматов.
Работа Эгри-Надя и Неханива (2005, 2008–) продолжает дальнейшую автоматизацию версии голономии разложения Крона – Родса, расширенной с помощью соответствующего разложения для конечных групп (так называемые координаты Фробениуса – Лагранжа ) с использованием системы компьютерной алгебры GAP .
Приложения вне теорий полугрупп и моноидов теперь вычислительно возможны. Они включают вычисления в биологии и биохимических системах (например, Egri-Nagy & Nehaniv 2008), искусственный интеллект , физику конечных состояний , психологию и теорию игр (см., Например, Rhodes 2009).
Смотрите также
Примечания
- ^ Холкомб (1982)стр. 141-142
- ^ Дж. Родс, основной доклад на Международной конференции по полугруппам и алгебраической инженерии ( Айдзу , Япония ), 26 марта 1997 г.
- ^ Моррис В. Хирш , "Предисловие к приложениям Родса теории автоматов и алгебры ". В книге Дж. Родса, Приложения теории автоматов и алгебры: через математическую теорию сложности к биологии, физике, философии и играм », (ред. К.Л. Неханив), World Scientific Publishing Co., 2010.
использованная литература
- Баррингтон, Дэвид А. Микс (1992). «Некоторые задачи с многочленами Разборова-Смоленского». В Патерсоне, штат Массачусетс (ред.). Сложность булевой функции, сел. Пап. Symp., Дарем / Великобритания, 1990 . Серия конспектов лекций Лондонского математического общества. 169 . С. 109–128. ISBN 978-0-521-40826-4. Zbl 0769.68041 .
- Дикерт, Фолькер; Куфлейтнер, Манфред; Стейнберг, Бенджамин (2012). "Теорема Крона-Родса и локальные делители". Fundamenta Informaticae . 116 (1–4): 65–77. arXiv : 1111.1585 . DOI : 10,3233 / FI-2012-669 . ISSN 0169-2968 .
- Пал Дёмёси; Кристофер Л. Неханив (2005). Алгебраическая теория сетей автоматов: Введение . Монографии SIAM по дискретной математике и приложениям. Общество промышленной и прикладной математики. ISBN 978-0-89871-569-9.
- Egri-Nagy, A .; и Неханив, С.Л. (2005), «Алгебраическая иерархическая декомпозиция конечных автоматов: сравнение реализаций теории Крона – Родса», на 9-й Международной конференции по реализации и применению автоматов (CIAA 2004), Кингстон, Канада, 22–24 июля. , 2004, Пересмотренные избранные статьи , Редакторы: Домарацки, М .; Охотин, А .; Salomaa, K .; и другие. ; Лекционные заметки Springer по информатике , Vol. 3317, стр. 315–316, 2005 г.
- Эгри-Надь, Аттила; Неханив, Кристофер Л. (лето 2008 г.). «Иерархические системы координат для понимания сложности и ее развития с приложениями к генетическим регуляторным сетям» (PDF) . Искусственная жизнь . 14 (3): 299–312. DOI : 10.1162 / artl.2008.14.3.14305 . ЛВП : 2299/16600 . ISSN 1064-5462 . PMID 18489252 .
- Эйленберг, Самуэль (1976). Автоматы, языки и машины . Чистая и прикладная математика, Конспект лекций по математике. Нью-Йорк: Academic Press. ISBN 978-0-12-234001-7. Две главы написаны Бретом Тилсоном.
- Эсик, З. (март 2000 г.). «Доказательство теоремы Крона – Родса о разложении» . Теоретическая информатика . 234 (1–2): 287–300. DOI : 10.1016 / s0304-3975 (99) 00315-1 . ISSN 0304-3975 .
- Хартманис, Юрис ; Стернс, Р. Э. (1966). Теория алгебраической структуры последовательных машин . Прентис-Холл. ASIN B0006BNWTE .
- Холкомб, WML (1982). Теория алгебраических автоматов . Кембриджские исследования в области высшей математики. 1 . Издательство Кембриджского университета . ISBN 978-0-521-60492-5. Zbl 0489.68046 .
- Камбитес, Марк (2007). «О сложности Крона – Родса полугрупп верхнетреугольных матриц». Международный журнал алгебры и вычислений . 17 (1): 187–201. CiteSeerX 10.1.1.657.4000 . DOI : 10.1142 / S0218196707003548 . ISSN 0218-1967 .
- Крон, КР; и Родс, Дж. Л. (1962), "Алгебраическая теория машин", Труды симпозиума по математической теории автоматов (редактор: Фокс, Дж.), ( Wiley – Interscience )
- Крон, Кеннет; Родс, Джон (апрель 1965 г.). "Алгебраическая теория машин. I. Теорема разложения на простые числа для конечных полугрупп и машин" (PDF) . Труды Американского математического общества . 116 : 450–464. DOI : 10.2307 / 1994127 . ISSN 0002-9947 . JSTOR 1994127 . Проверено 18 сентября 2010 года .
- Крон, Кеннет; Родс, Джон Л. (август 1968 г.). Арбиб, Майкл А. (ред.). Алгебраическая теория машин, языков и полугрупп . Академическая пресса. ISBN 978-0-12-059050-6.
- Лаллеман, Жерар (1971-03-01). «О теореме разложения на простые числа конечных моноидов». Теория вычислительных систем . 5 (1): 8–12. DOI : 10.1007 / BF01691462 . ISSN 1433-0490 .
- Мейер, АР; Томпсон, К. (1969-06-01). «Замечания об алгебраической декомпозиции автоматов» (PDF) . Теория вычислительных систем . 3 (2): 110–118. CiteSeerX 10.1.1.649.4716 . DOI : 10.1007 / BF01746516 . ISSN 1432-4350 .
- Джон Роудс; Бенджамин Стейнберг (17 декабря 2008 г.). Q-теория конечных полугрупп . Springer Verlag. ISBN 978-0-387-09780-0.
- Штраубинг, Ховард; Териен, Дени (2002). «Слабо повторяющиеся блочные произведения конечных моноидов» . В Raisbaum, Серджио (ред.). Конспект лекций по информатике . ЛАТИН 2002: Теоретическая информатика. 2286 . Берлин: Springer. С. 91–104. DOI : 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. DOI : 10.1016 / 0022-4049 (87) 90108-3 . ISSN 0022-4049 .
- Уэллс, К. (1980). «Теорема Крона – Родса для категорий» . Журнал алгебры . 64 : 37–45. DOI : 10.1016 / 0021-8693 (80) 90130-1 . ISSN 0021-8693 .
- Зейгер, HP (апрель 1967 г.). «Каскадный синтез конечных автоматов» . Информация и контроль . 10 (4): 419–433. DOI : 10.1016 / S0019-9958 (67) 90228-8 . ISSN 1462-3889 .Исправление: информация и контроль 11 (4): 471 (1967), плюс исправление.
дальнейшее чтение
- Родс, Джон Л. (2010). Кристофер Л. Неханив (ред.). Приложения теории автоматов и алгебры: через математическую теорию сложности в биологии, физике, психологии, философии и играх . ISBN World Scientific Pub Co Inc. 978-981-283-696-0.
- Родос, Джон ; Стейнберг, Бенджамин (17 декабря 2008 г.). Q-теория конечных полугрупп . Springer Verlag. ISBN 978-0-387-09780-0.
- Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схем . Успехи теоретической информатики. Базель: Биркхойзер. ISBN 978-3-7643-3719-3. Zbl 0816.68086 .
внешние ссылки
- Проф. Джон Л. Родс, веб-страница Калифорнийского университета в Беркли
- SgpDec: Иерархическая композиция и разложение групп перестановок и полугрупп преобразований , разработанная А. Эгри-Надь и К. Л. Неханив . Пакет программного обеспечения с открытым исходным кодом для системы компьютерной алгебры GAP .
- Джон Л. Родс (2010). Кристофер Л. Неханив (ред.). Приложения теории автоматов и алгебры: через математическую теорию сложности в биологии, физике, психологии, философии и играх . ISBN World Scientific Pub Co Inc. 978-981-283-696-0.
- Введение в теорему Крона-Родса (раздел 5); часть МООК « Введение в перенормировку» Института Санта-Фе. Автор Саймон ДеДео.