## Probabilistic automata of bounded ambiguity

### 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