Alternating Weighted Automata
Krishnendu Chatterjee, Laurent Doyen and Thomas A. Henzinger
Abstract
Weighted automata are finite automata with numerical weights on
transitions. Nondeterministic weighted automata define quantitative
languages L that assign to each word w a real number L(w) computed as
the maximal value of all runs over w, and the value of a run r is a
function of the sequence of weights that appear along r. There are
several natural functions to consider such as Max, LimSup, LimInf, limit
average, and discounted sum of transition weights.
We introduce alternating weighted automata in which the transitions of
the runs are chosen by two players in a turn-based fashion. Each word is
assigned the maximal value of a run that the first player can enforce
regardless of the choices made by the second player. We survey the
results about closure properties, expressiveness, and decision problems
for nondeterministic weighted automata, and we extend these results to
alternating weighted automata.
For quantitative languages L_1 and L_2, we consider the pointwise
operations max(L_1,L_2), min(L_1,L_2), 1-L_1, and the sum L_1+L_2. We
establish the closure properties of all classes of alternating weighted
automata with respect to these four operations.
We next compare the expressive power of the various classes of
alternating and nondeterministic weighted automata over infinite words.
In particular, for limit average and discounted sum, we show that
alternation brings more expressive power than nondeterminism.
Finally, we present decidability results and open questions for the
quantitative extension of the classical decision problems in automata
theory: emptiness, universality, language inclusion, and language
equivalence.