Mixed Nondeterministic-Probabilistic Automata

Albert Benveniste (1) , Jean-Baptiste Raclet (2, 3)

1 HYCOMES - Modélisation hybride & conception par contrats pour les systèmes embarqués multi-physiques
2 IRIT-ACADIE - Assistance à la Certification d’Applications DIstribuées et Embarquées
3 UT3 - Université Toulouse III - Paul Sabatier

Graphical models in probability and statistics are a core concept in the area of probabilistic reasoning and probabilistic programming-graphical models include Bayesian networks and factor graphs. For modeling and formal verification of probabilistic systems, probabilistic automata were introduced. This paper proposes a coherent suite of models consisting of Mixed Systems, Mixed Bayesian Networks, and Mixed Automata, which extend factor graphs, Bayesian networks, and probabilistic automata with the handling of nondeterminism. Each of these models comes with a parallel composition, and we establish clear relations between these three models. Also, we provide a detailed comparison between Mixed Automata and Probabilistic Automata.

Keywords: Bayesian networks; Probabilistic programming; Probabilistic automata; Semantics; Nondeterminism and probability; Factor graphs

Domains: Formal Languages and Automata Theory [cs.FL]

Albert Benveniste, Jean-Baptiste Raclet. Mixed Nondeterministic-Probabilistic Automata: Blending graphical probabilistic models with nondeterminism. Discrete Event Dynamic Systems, 2023, 2023, pp.1-58. ⟨10.1007/s10626-023-00375-x⟩. ⟨hal-04276789⟩