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

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

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

Определение

Позволять ${ displaystyle N}$ быть моноид, подмножество ${ Displaystyle S substeq 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_ {п}}$, где каждый ${ 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 } = фи ^ {- 1} ( фи ( {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]

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

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

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

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

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

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