A Probabilistic Kleene TheoremReport as inadecuate




A Probabilistic Kleene Theorem - Download this document for free, or read online. Document in PDF available to download.

1 LSV - Laboratoire Spécification et Vérification Cachan 2 MEXICO - Modeling and Exploitation of Interaction and Concurrency LSV - Laboratoire Spécification et Vérification Cachan, ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643 3 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : We provide a Kleene Theorem for Rabin probabilistic automata over finite words. Probabilistic automata generalize deterministic finite automata and assign to a word an acceptance probability. We provide probabilistic expressions with probabilistic choice, guarded choice, concatenation, and a star operator. We prove that probabilistic expressions and probabilistic automata are expressively equivalent. Our result actually extends to two-way probabilistic automata with pebbles and corresponding expressions.

keyword : Probabilistic Automata Probabilistic Expressions Pebble Automata





Author: Benedikt Bollig - Paul Gastin - Benjamin Monmege - Marc Zeitoun -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents