Wprowadzenie do automatów probabilistycznych

Gdzie mogę znaleźć wprowadzenie do automatów probabilistycznych i co one rozpoznają (niektóre funkcje od słów do )? Czy istnieje standardowy termin określający takie funkcje, które są rozpoznawane przez automaty probabilistyczne, analogiczne do „zwykłych języków”, dla których rozpoznają deterministyczne automaty skończone (DFA)? $[0,1]$

Szukam czegoś, co podchodzi do tego analogicznie do badania podstawowych pytań na temat DFA i zwykłych języków, takich jak wyrazistość, zamknięcie i właściwości rozstrzygalności.

To i to nie wydaje się być tym, czego szukam.

reference-request fl.formal-languages probabilistic-automata Prateek
źródło

Są to „pozytywne wsparcie” racjonalnej serii , tj. Języki dla takiej serii. Jednak nie jest to zbyt dobrze wychowane. Studiowałem zamknięcie logiczne tej klasy, jeśli jesteś zainteresowany: eccc.hpi-web.de/report/2013/040 .

Z

$\mathbb{Z}$

{w ∣ (r, w) > 0}

$\{w \mid (r, w) > 0\}$

r

$r$

Michaël Cadilhac

Odpowiedzi:

Pierwszy artykuł Rabin (1963) daje podstawy tego, czego szukasz. Klasa języków rozpoznawana przez automaty probabilistyczne (z punktem odcięcia) nazywana jest językami stochastycznymi.

Niech będzie automatem probabilistycznym zdefiniowanym na alfabecie a będzie prawdopodobieństwem akceptacji na wejściu . Następnie z punktem odcięcia definiuje następujący język: $P$ $\Sigma$ $f_P(w)$ $P$ $w \in \Sigma^*$ $P$ $\lambda \in [0,1)$

$L(P,\lambda) = \{ w \in \Sigma^* \mid f_P(w) > \lambda \}$ .

Należy zauważyć, że rozpoznanie za pomocą punktu odcięcia można uznać za rozpoznanie z nieograniczonym błędem. W przypadku błędu ograniczonego (lub izolowanego punktu odcięcia) automaty probabilistyczne mogą rozpoznać wszystkie i tylko zwykłe języki.

Książka Paza (1971) i ankieta Bukharaeva (1980) są dobrymi referencjami.

Możesz także sprawdzić ostatnią ankietę na temat automatów kwantowych, w której można prześledzić niektóre odniesienia do automatów probabilistycznych.

Abuzer Yakaryilmaz
źródło