Online Space Complexity of Probabilistic Languages

Nathanaël Fijalkow

Logical Foundations of Computer Science, Deerfield Beach, January 6th, 2016

Probabilistic Automata

$$P_{\mathcal{A}}(a_1 \cdots a_n) = \frac{a_1}{2^n} + \cdots + \frac{a_n}{2^1}$$

Online Complexity

For a fixed $L \subseteq A^*$,

what is the size of the smallest data structure maintaining the answer to the Boolean query "is the prefix in $L$?"

Karp (67): consider infinite automata, the size is the number of different states after reading $n$ letters

language	online complexity
regular	constant
$\{w \mid \|w\|_a = \|w\|_b\}$	linear
$\{w \mid \|w\|_a = \|w\|_b = \|w\|_c\}$	quadratic
$\{w w \mid w \in A^*\}$	exponential

Myhill-Nerode point of view

The size of the minimal deterministic automaton for $L$ is given by the Myhill-Nerode equivalence classes: $$u \sim v \Longleftrightarrow \forall w, \quad (uw \in L \leftrightarrow vw \in L)$$

Count the number of equivalence classes for $A^{\le n}$.

Theorem: there exists a probabilistic automaton with exponential online complexity!

$$P_{\mathcal{A}}(u \sharp v) = \mathrm{bin}(u) \cdot \mathrm{bin}(v)$$

After reading $u 1 \sharp$ and $u' 1 \sharp$, the two states must be different:
Indeed, there exists $v$ such that $$\begin{cases} \mathrm{bin}(u 1) \cdot \mathrm{bin}(v) < \frac{1}{2} \\ \mathrm{bin}(u' 1) \cdot \mathrm{bin}(v) > \frac{1}{2} \end{cases}$$