## Quantitative Languages

*Krishnendu Chatterjee, Laurent Doyen, and
Thomas A. Henzinger*

Quantitative generalizations of classical languages, which assign to
each word a real number instead of a boolean value, have applications
in modeling resource-constrained computation. We use weighted
automata (finite automata with transition weights) to define several
natural classes of quantitative languages over finite and infinite
words; in particular, the real value of an infinite run is computed as
the maximum, limsup, liminf, limit average, or discounted sum of the
transition weights. We define the classical decision problems of
automata theory (emptiness, universality, language inclusion, and
language equivalence) in the quantitative setting and study their
computational complexity. As the decidability of language inclusion
remains open for some classes of weighted automata, we introduce a
notion of quantitative simulation that is decidable and implies
language inclusion. We also give a complete characterization of the
expressive power of the various classes of weighted automata. In
particular, we show that most classes of weighted automata cannot be
determinized.

*Proceedings of the
17th International Conference on Computer Science Logic*
(CSL),
Lecture Notes in Computer Science 5213,
Springer,
2008,
pp. 385-400.

Download inofficial, sometimes updated
PostScript /
PDF document.
© 2008 Springer.