Введение в вероятностные автоматы

10

Где я могу найти введение в вероятностные автоматы и что они распознают (определенные функции из слов в )? Существует ли стандартный термин для таких функций, которые распознаются вероятностными автоматами, аналогично «обычным языкам» для того, что распознают детерминированные конечные автоматы (DFA)?[0,1]

Я ищу что-то похожее на изучение базовых вопросов по DFA и обычным языкам, таких как свойства выразительности, замыкания и разрешимости.

Это и это не совсем то, что я ищу.

Prateek
источник
Они являются «положительными носителями» рациональных рядов, т. Е. Языков { w ( r , w ) > 0 } для r такого ряда. Хотя это не слишком хорошо. Я изучал логическое замыкание этого класса, если вам интересно: eccc.hpi-web.de/report/2013/040 . Z{w(r,w)>0}r
Михаэль Кадилхак,

Ответы:

9

Первая статья Рабина (1963) дает основы того, что вы ищете. Класс языков, распознаваемых вероятностными автоматами (с точкой среза), называется стохастическими языками.

PΣfP(w)PwΣPλ[0,1)

L(P,λ)={wΣfP(w)>λ}

Заметьте, что распознавание с точкой отсечения можно рассматривать как распознавание с неограниченной ошибкой. В случае ограниченной ошибки (или изолированной точки отсечения) вероятностные автоматы могут распознавать все и только обычные языки.

Книга Паз (1971) и обзор Бухараева (1980) являются хорошими ссылками.

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

Абузер Якарылмаз
источник