Автоматическая полугруппа - Automatic semigroup - Wikipedia

В математика, автоматическая полугруппа является конечно порожденным полугруппа оснащен несколькими обычные языки над алфавитом, представляющим генераторную установку. Один из этих языков определяет «канонические формы» для элементов полугруппы, другие языки определяют, представляют ли две канонические формы элементы, которые различаются умножением на генератор.

Формально пусть ${\displaystyle S}$ быть полугруппой и ${\displaystyle A}$ - конечный набор образующих. Затем автоматическая структура за ${\displaystyle S}$ относительно ${\displaystyle A}$ состоит из обычного языка ${\displaystyle L}$ над ${\displaystyle A}$ так что каждый элемент ${\displaystyle S}$ имеет хотя бы одного представителя в ${\displaystyle L}$ и такой, что для каждого ${\displaystyle a\in A\cup \{\varepsilon \}}$, отношение, состоящее из пар ${\displaystyle (u,v)}$ с ${\displaystyle ua=v}$ является регулярным, рассматриваемым как подмножество (А^# × А^#) *. Здесь А^# является А дополнен символом заполнения.^[1]

Понятие автоматической полугруппы было обобщено из автоматические группы Кэмпбелл и др. (2001)

В отличие от автоматических групп (см. Эпштейн и др., 1992), полугруппа может иметь автоматическую структуру по отношению к одной образующей, но не по отношению к другой. Однако, если автоматическая полугруппа имеет идентичность, то она имеет автоматическую структуру по отношению к любому генерирующему набору (Duncan et al. 1999).

Проблемы с решением

Как и автоматические группы, автоматические полугруппы имеют проблема со словом разрешима за квадратичное время. Kambites & Otto (2006) показали, что неразрешимо, обладает ли элемент автоматического моноида правым обратным.

Каин (2006) доказал, что для автоматических полугрупп неразрешимы как канцелярская, так и левая канцелярия. С другой стороны, для автоматических полугрупп разрешима правая сокращаемость (Silva & Steinberg 2004).

Геометрическая характеристика

Автоматические структуры для групп имеют элегантную геометрическую характеристику, называемую собственность попутчика (Эпштейн и др., 1992, гл. 2). Автоматические структуры для полугрупп владеть свойство попутчика, но в целом им не охарактеризовано (Campbell et al. 2001). Однако эту характеристику можно обобщить на некоторыегруппа -подобные классы полугрупп, а именно совершенно простые полугруппы (Кэмпбелл и др., 2002) и полугруппы, встраиваемые в группы (Каин и др., 2006).

Примеры автоматических полугрупп

• Бициклический моноид
• Конечно порожденные подполугруппы свободная полугруппа

Рекомендации

1. Кэмпбелл, Колин М .; Робертсон, Эдмунд Ф .; Рускук, Ник; Томас, Ричард М. (2001), «Автоматические полугруппы» (PDF), Теоретическая информатика, 250 (1–2): 365–391, Дои:10.1016 / S0304-3975 (99) 00151-6.

• Каин, Алан Дж. (2006), «Канцелярская способность неразрешима для автоматических полугрупп», Ежеквартальный математический журнал, 57 (3): 285–295, CiteSeerX  10.1.1.106.6068, Дои:10.1093 / qmath / hai023
• Каин, Алан Дж .; Робертсон, Эдмунд Ф .; Рускук, Ник (2006), "Подполугруппы групп: представления, представления Мальцева и автоматические структуры", Журнал теории групп, 9 (3): 397–426, Дои:10.1515 / JGT.2006.027.
• Кэмпбелл, Колин М .; Робертсон, Эдмунд Ф .; Рускук, Ник; Томас, Ричард М. (2002), "Автоматические полностью простые полугруппы", Acta Mathematica Hungarica, 95 (3): 201–215, Дои:10.1023 / А: 1015632704977.
• Дункан, А. Дж .; Робертсон, Э. Ф .; Рускук, Н. (1999), "Автоматические моноиды и замена генераторов", Математические труды Кембриджского философского общества, 127 (3): 403–409, Дои:10.1017 / S0305004199003722.
• Эпштейн, Дэвид Б.А.; Кэннон, Джеймс У.; Холт, Дерек Ф .; Леви, Сильвио В. Ф .; Патерсон, Майкл С.; Терстон, Уильям П. (1992), Обработка текста в группах, Бостон, Массачусетс: Издательство "Джонс и Бартлетт", ISBN  0-86720-244-0.
• Камбитес, Марк; Отто, F (2006), "Проблемы с равномерным решением для автоматических полугрупп", Журнал алгебры, 303 (2): 789–809, arXiv:математика / 0509349, Дои:10.1016 / j.jalgebra.2005.11.028
• Silva, P.V .; Стейнберг, Б. (2004), "Геометрическая характеристика автоматических моноидов", Ежеквартальный математический журнал, 55 (3): 333–356, CiteSeerX  10.1.1.36.1681, Дои:10.1093 / qmath / hah006

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

• Хоффманн, Майкл; Куске, Дитрих; Отто, Фридрих; Томас, Ричард М. (2002), «Некоторые родственники автоматических и гиперболических групп», в Gomes, Gracinda M. S. (ed.), Полугруппы, алгоритмы, автоматы и языки. Материалы семинаров, проведенных в Международном центре математики, CIM, Коимбра, Португалия, май, июнь и июль 2001 г., Сингапур: World Scientific, стр. 379–406, Zbl  1031.20047