Online Complexity
Nathanaël Fijalkow
Highlights'2015, Prague
Online Complexity
$$L \subseteq A^*$$
size of the smallest data structure maintaining the answer to the Boolean query
"is the prefix in $L$?"
the size is the number of different states after reading $n$ letters
| language | online complexity |
|---|---|
$\{a^n b^n \mid n \in \mathbb{N}\}$ |
linear |
$\{w \mid |w|_a = |w|_b = |w|_c\}$ |
quadratic |
$\{w w \mid w \in A^*\}$ |
exponential |
Online complexity is not:
- dynamic complexity
- competitive ratios of online algorithms
- streaming algorithms
Theorem:
- a language is regular if, and only if, it has constant online complexity,
- all languages have exponential online complexity.
Online Complexity
Probabilistic Automata
Rabin (63): can we compute the acceptance probability in an online fashion?
$$\mathbb{P}(u \sharp v) = bin(u) \cdot bin(v)$$
$$L = \left\{ u \sharp v \mid bin(u) \cdot bin(v) > \frac{1}{2}\right\}$$
Theorem: this probabilistic automaton has exponential online complexity
Online Complexity
Research Directions
- a dichotomy theorem: every probabilistic automaton has either polynomial or exponential online complexity,
- probabilistic automata exactly correspond to constant approximated online complexity,
- logical characterisations of languages of linear, quadratic and polynomial online complexity.