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

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

Формально пусть быть полугруппой и - конечный набор образующих. Затем автоматическая структура за относительно состоит из обычного языка над так что каждый элемент имеет хотя бы одного представителя в и такой, что для каждого , отношение, состоящее из пар с является регулярным, рассматриваемым как подмножество (А# × А#) *. Здесь А# является А дополнен символом заполнения.[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.

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

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