Introduction aux automates probabilistes

Où puis-je trouver une introduction aux automates probabilistes et ce qu'ils reconnaissent (certaines fonctions des mots à )? Existe-t-il un terme standard pour ces fonctions qui sont reconnues par les automates probabilistes, analogue aux «langages normaux» pour ce que les automates déterministes finis (DFA) reconnaissent?$[0,1]$

Je cherche quelque chose qui l'aborde de manière analogue à l'étude des questions de base sur les DFA et les langages réguliers, comme l'expressivité, la fermeture et les propriétés de décidabilité.

Ceci et cela ne semble pas vraiment être ce que je recherche.

Le premier article de Rabin (1963) donne les bases de ce que vous recherchez. La classe de langages reconnue par les automates probabilistes (avec point de coupure) est appelée langages stochastiques.

Soit un automate probabiliste défini sur l'alphabet et la probabilité d'acceptation de sur l'entrée . Ensuite, avec le point de coupure définit le langage suivant:Σ f P ( w ) P w ∈ Σ ∗ P λ ∈ [ 0 , 1 $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 \}$ .

Remarquez que la reconnaissance avec point de coupure peut être vue comme une reconnaissance avec erreur illimitée. En cas d'erreur bornée (ou de point de coupure isolé), les automates probabilistes peuvent reconnaître toutes et seulement les langues normales.

Le livre de Paz (1971) et l'enquête de Boukharaev (1980) sont de bonnes références.

Vous pouvez également consulter une enquête récente sur les automates quantiques où vous pouvez retrouver quelques références sur les automates probabilistes.