Introducción a los autómatas probabilísticos.

¿Dónde puedo encontrar una introducción a los autómatas probabilísticos y lo que reconocen (ciertas funciones desde palabras hasta )? ¿Existe un término estándar para tales funciones que son reconocidas por los autómatas probabilísticos, análoga a "lenguajes regulares" para lo que reconocen los autómatas finitos deterministas (DFA)? $[0,1]$

Estoy buscando algo que lo aborde de manera análoga al estudio de preguntas básicas sobre DFA y lenguajes regulares, como las propiedades de expresividad, cierre y capacidad de decisión.

Esto y esto no parecen ser lo que estoy buscando.

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

Son los "soportes positivos" de las series racionales

, es decir, los lenguajes

para

tales series. Sin embargo, esto no se comporta demasiado bien. Estudié el cierre booleano de esta clase, si está interesado: eccc.hpi-web.de/report/2013/040 .

Z

$\mathbb{Z}$

{w ∣ (r, w) > 0}

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

r

$r$

Michaël Cadilhac

Respuestas:

El primer artículo de Rabin (1963) brinda los conceptos básicos de lo que está buscando. La clase de idiomas reconocida por los autómatas probabilísticos (con punto de corte) se llama lenguajes estocásticos.

Sea un autómata probabilístico definido en el alfabeto y sea la probabilidad de aceptación de en la entrada . Entonces, con punto de corte define el siguiente lenguaje: $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 el reconocimiento con punto de corte puede verse como un reconocimiento con error ilimitado. En caso de error acotado (o punto de corte aislado), los autómatas probabilísticos pueden reconocer todos y solo los lenguajes regulares.

El libro de Paz (1971) y la encuesta de Bukharaev (1980) son buenas referencias.

También puede consultar una encuesta reciente sobre autómatas cuánticos donde puede rastrear algunas referencias sobre autómatas probabilísticos.

Abuzer Yakaryilmaz
fuente