Probabilistic automata of bounded ambiguity
Nathanaël Fijalkow,
Cristian Riveros, James Worrell
CNRS, LaBRI, and Alan Turing Institute, London, and University of Warwick
University of Warwick, March 13th, 2018

$$\mathbb{P}(\text{train train predict}) = 0.4 \cdot 0.6 \cdot 1\ +\ 0.6 \cdot 0.45 \cdot 1$$
A probabilistic automaton induces $\mathbb{P} : A^* \to [0,1]$
Goal: algorithmically
determine the properties of $\mathbb{P}$
In this paper: emptiness problem
$$\exists w \in A^*,\ \mathbb{P}(w) \ge \frac{1}{2}$$
Many models somehow embed:
- HMM: Hidden Markov Models
- PSR: Predictive State Representations
- OOM: Observable Operator Models
Ambiguity
An automaton has
ambiguity $f : \mathbb{N} \to \mathbb{N}$ if each word of length $n$ have at most $f(n)$
accepting runs.
Undecidability
This automaton computes the binary value function and is
linearly ambiguous:
undecidability follows for emptiness, universality, isolation with
infinite ambiguity
Results
Emptiness:
- in NEXPTIME and PSPACE-hard for finitely ambiguous
- PSPACE-complete if the ambiguity is polynomially bounded in the number of states
- in NP for $k$-ambiguous, for every constant $k$
- in quasi-polynomial time $O(n^{\log(n)})$ for 2-ambiguous
Approximation of emptiness:
- no polynomial time approximation for finitely ambiguous unless P = NP
- polynomial time approximation for $k$-ambiguous, for every constant $k$
Stochastic path problem
value of the red path: $.4 \times .9 \times .9\ +\ .6 \times .1 \times .9 = .27$.
Input: a graph and a threshold $c$
Question: does there exist a path from $s$ to $t$ whose value is at least $c$?
Reduction
Given a $k$-ambiguous probabilistic automaton with $n$ states,
we construct a graph with $O(n^k)$ vertices such that:
- path $\implies$ $k$ accepting runs of some word,
- $k$ accepting runs of a word $\implies$ path
TL;DR:
emptiness of $k$-ambiguous reduces to
$k$-stochastic path problem
(Convex) Pareto curves
Theorem: quasi-polynomial time algorithm returns a convex Pareto curve for the bi-stochastic path problem
Corollary: quasi-polynomial time algorithm for emptiness of 2-ambiguous probabilistic automata
Approximate Pareto curves
Theorem: polynomial time algorithm returns a convex $\varepsilon$-Pareto curve for the $k$-stochastic path problem
Corollary: polynomial time algorithm for approximation of the emptiness of $k$-ambiguous probabilistic automata