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

О других значениях слова «узнаваемый» см. Узнаваемый (значения).

В Информатика, точнее в теория автоматов, а узнаваемый набор из моноид - это подмножество, которое может быть выделено некоторым морфизмом в конечный моноид. Узнаваемые множества полезны в теории автоматов, формальные языки и алгебра.

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

Определение

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

Пример

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

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

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

Подмножество ${\displaystyle N}$ узнаваем тогда и только тогда, когда его синтаксический моноид конечно.

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

• союз
• пересечение
• дополнять
• верно и левое частное

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

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

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

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

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

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

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

Смотрите также

• Рациональный набор
• Рациональный моноид

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

1. Джон Микин (2007). «Группы и полугруппы: связи и противопоставления». В C.M. Кэмпбелл; М.Р. Квик; Э. Ф. Робертсон; G.C. Смит (ред.). Группы Сент-Эндрюс 2005 Том 2. Издательство Кембриджского университета. п. 376. ISBN  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. Zbl  1188.68177.