# Mixed Nondeterministic-Probabilistic Automata: Blending graphical probabilistic models with nondeterminism

arXiv: https://arxiv.org/abs/2201.07474 · HTML: https://mlsanity.com/paper/2201.07474/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 73 references that are in the map.
- First posted on arXiv 19 Jan 2022.

## Builds on (most cited first, 15 of 15)

- [An Introduction to Probabilistic Programming](https://mlsanity.com/paper/1809.10756/) (2018)
- [A Lambda-Calculus Foundation for Universal Probabilistic Programming](https://mlsanity.com/paper/1512.08990/) (2015)
- [Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints](https://mlsanity.com/paper/1601.04943/) (2016)
- [Probabilistic Programs with Stochastic Conditioning](https://mlsanity.com/paper/2010.00282/) (2020)
- [Reactive Probabilistic Programming](https://mlsanity.com/paper/1908.07563/) (2019)
- [Measure Transformer Semantics for Bayesian Machine Learning](https://mlsanity.com/paper/1308.0689/) (2013)
- [Semantics of higher-order probabilistic programs with conditioning](https://mlsanity.com/paper/1902.11189/) (2019)
- [Conditioning in Probabilistic Programming](https://mlsanity.com/paper/1504.00198/) (2015)
- [Relational reasoning via probabilistic coupling](https://mlsanity.com/paper/1509.03476/) (2015)
- [Concurrency and Probability: Removing Confusion, Compositionally](https://mlsanity.com/paper/1710.04570/) (2017)
- [Correctness by construction for probabilistic programs](https://mlsanity.com/paper/2007.15246/) (2020)
- [Markov two-components processes](https://mlsanity.com/paper/1305.5239/) (2013)
- [Stochastic Nondeterminism and Effectivity Functions](https://mlsanity.com/paper/1405.7141/) (2014)
- [Synchronization of Bernoulli sequences on shared letters](https://mlsanity.com/paper/1506.06537/) (2015)
- [Probabilistic Couplings for Probabilistic Reasoning](https://mlsanity.com/paper/1710.09951/) (2017)

## Abstract (arXiv)

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. In this paper we develop a new model of mixed (nondeterministic/probabilistic) automata that subsumes both nondeterministic automata and graphical probabilistic models. Mixed Automata are equipped with parallel composition, simulation relation, and support message passing algorithms inherited from graphical probabilistic models. Segala's Probabilistic Automatacan be mapped to Mixed Automata.