Узнаваемый набор

В информатике , точнее в теории автоматов , распознаваемое множество моноида гомоморфизмом которое можно отличить некоторым — это подмножество , до конечного моноида. Распознаваемые множества полезны в теории автоматов, формальных языках и алгебре .

Это понятие отличается от понятия узнаваемого языка . Действительно, термин «узнаваемый» имеет в теории вычислимости другое значение .

Определение

Позволять $N$ быть моноидом , подмножеством $S\subseteq N$ распознается моноидом $M$ если существует гомоморфизм $\phi$ от $N$ к $M$ такой, что $S=\phi ^{-1}(\phi (S))$ , и распознаваем, если он распознается некоторым конечным моноидом. Это означает, что существует подмножество $T$ из $M$ (не обязательно субмоноид $M$ ) такой, что образ $S$ находится в $T$ и образ $N\setminus S$ находится в $M\setminus T$ .

Пример

Позволять $A$ быть алфавитом : множество $A^{*}$ слов более $A$ является моноидом, свободным моноидом на $A$ . Узнаваемые подмножества $A^{*}$ это именно обычные языки . Действительно, такой язык распознается моноидом перехода любого автомата, распознающего этот язык.

Узнаваемые подмножества $\mathbb {N}$ являются в конечном счете периодическими наборами целых чисел.

Характеристики

Подмножество $N$ распознаваем тогда и только тогда, когда его синтаксический моноид конечен.

Набор $\mathrm {REC} (N)$ узнаваемых подмножеств $N$ закрыт под:

Теорема Мезеи ^{[ нужна ссылка ]} утверждает, что если $M$ является произведением моноидов $M_{1},\dots ,M_{n}$ , то подмножество $M$ распознаваем тогда и только тогда, когда оно представляет собой конечное объединение подмножеств вида $R_{1}\times \cdots \times R_{n}$ , где каждый $R_{i}$ является узнаваемым подмножеством $M_{i}$ . Например, подмножество $\{1\}$ из $\mathbb {N}$ является рациональным и, следовательно, узнаваемым, поскольку $\mathbb {N}$ является свободным моноидом. Отсюда следует, что подмножество $S=\{(1,1)\}$ из $\mathbb {N} ^{2}$ узнаваем.

Теорема Макнайта ^{[ нужна ссылка ]} утверждает, что если $N$ то конечно порождено, его распознаваемые подмножества являются рациональными подмножествами . В целом это неверно, поскольку вся $N$ всегда узнаваем, но он нерационален, если $N$ генерируется бесконечно.

И наоборот, рациональное подмножество может быть не распознаваемо, даже если $N$ конечно порождено. Фактически, даже конечное подмножество $N$ не обязательно узнаваем. Например, набор $\{0\}$ не является узнаваемым подмножеством $(\mathbb {Z} ,+)$ . Действительно, если гомоморфизм $\phi$ от $\mathbb {Z}$ к $M$ удовлетворяет $\{0\}=\phi ^{-1}(\phi (\{0\}))$ , затем $\phi$ — инъективная функция ; следовательно $M$ бесконечен.

Также, в целом, $\mathrm {REC} (N)$ не закрыт под звездой Клини . Например, набор $S=\{(1,1)\}$ является узнаваемым подмножеством $\mathbb {N} ^{2}$ , но $S^{*}=\{(n,n)\mid n\in \mathbb {N} \}$ не узнаваем. Действительно, его синтаксический моноид бесконечен.

Пересечение рационального подмножества и распознаваемого подмножества является рациональным.

Распознаваемые множества замкнуты относительно обратных гомоморфизмов. Т.е. если $N$ и $M$ являются моноидами и $\phi :N\rightarrow M$ является гомоморфизмом, то если $S\in \mathrm {REC} (M)$ затем $\phi ^{-1}(S)=\{x\mid \phi (x)\in S\}\in \mathrm {REC} (N)$ .

Для конечных групп хорошо известен следующий результат Анисимова и Зейферта: подгруппа H конечно порожденной группы G узнаваема тогда и только тогда, когда H имеет конечный индекс в G . Напротив, H является рациональным тогда и только тогда, когда H конечно порождено. ^[1]

См. также

Ссылки

^ Джон Микин (2007). «Группы и полугруппы: связи и контрасты». В CM Кэмпбелл; мистер Квик; Э. Ф. Робертсон; Г. К. Смит (ред.). Группы Сент-Эндрюс 2005 Том 2 . Издательство Кембриджского университета. п. 376. ИСБН 978-0-521-69470-4 . препринт

Дикерт, Волкер; Куфлейтнер, Манфред; Розенберг, Герхард; Хертрампф, Ульрих (2016). «Глава 7: Автоматы». Дискретные алгебраические методы . Берлин/Бостон: Walter de Gruyther GmbH. ISBN 978-3-11-041332-8 .
Жан-Эрик Пен , Математические основы теории автоматов , Глава IV: Узнаваемые и рациональные множества

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

Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Кембридж: Издательство Кембриджского университета. Часть II: Сила алгебры. ISBN 978-0-521-84425-3 . Збл 1188.68177 .

[Campbell2007-1] Джон Микин (2007). «Группы и полугруппы: связи и контрасты». В CM Кэмпбелл; мистер Квик; Э. Ф. Робертсон; Г. К. Смит (ред.). Группы Сент-Эндрюс 2005 Том 2 . Издательство Кембриджского университета. п. 376. ИСБН 978-0-521-69470-4 . препринт

[1]