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


An automaton has ambiguity $f : \mathbb{N} \to \mathbb{N}$ if each word of length $n$ have at most $f(n)$ accepting runs.


This automaton computes the binary value function and is linearly ambiguous: undecidability follows for emptiness, universality, isolation with infinite ambiguity



Approximation of emptiness:

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$?


Given a $k$-ambiguous probabilistic automaton with $n$ states, we construct a graph with $O(n^k)$ vertices such that:

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