Introdução aos autômatos probabilísticos

Onde posso encontrar uma introdução aos autômatos probabilísticos e o que eles reconhecem (certas funções de palavras a )? Existe um termo padrão para essas funções que são reconhecidas por autômatos probabilísticos, análogos a "linguagens regulares" para o que os autômatos finitos determinísticos (DFAs) reconhecem? $[0,1]$

Estou procurando algo que se aproxime de maneira análoga ao estudo de perguntas básicas sobre DFAs e linguagens regulares, como propriedades de expressividade, fechamento e capacidade de decisão.

Isso e isso não parecem exatamente o que estou procurando.

reference-request fl.formal-languages probabilistic-automata Prateek
fonte

Eles são os "suportes positivos" das séries racionais

, ou seja, os idiomas

para

dessa série. Isso não é tão bem comportado, no entanto. Estudei o fechamento booleano desta classe, se você estiver interessado: eccc.hpi-web.de/report/2013/040 .

Z

$\mathbb{Z}$

{w ∣ (r, w) > 0}

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

r

$r$

Michaël Cadilhac

Respostas:

O primeiro artigo de Rabin (1963) fornece o básico do que você está procurando. A classe de idiomas reconhecida pelos autômatos probabilísticos (com ponto de corte) é chamada de linguagem estocástica.

$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 \}$

Observe que o reconhecimento com ponto de corte pode ser visto como reconhecimento com erro ilimitado. No caso de erro limitado (ou ponto de corte isolado), os autômatos probabilísticos podem reconhecer todos e apenas os idiomas regulares.

O livro de Paz (1971) e a pesquisa de Bukharaev (1980) são boas referências.

Você também pode verificar uma pesquisa recente sobre autômatos quânticos, onde pode rastrear algumas referências sobre autômatos probabilísticos.

Abuzer Yakaryilmaz
fonte