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