Title: Reasoning about Online Algorithms with Weighted Automata

Orna Kupferman, Hebrew University

Abstract:
We describe an automata-theoretic approach for the competitive
analysis of {\em online algorithms}. Our approach is based on {\em
weighted automata}, which assign to each input word a cost in
$\R^{\geq 0}$. By relating the ``unbounded look ahead'' of optimal
offline algorithms with nondeterminism, and relating the ``no look
ahead'' of online algorithms with determinism, we are able to solve
problems about the competitive ratio of online algorithms, and the
memory they require, by reducing them to questions about {\em
 determinization\/} and {\em approximated determinization} of
weighted automata.

Joint work with Benjamin Aminof and Robby Lampert.