The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.
The seminar is open to public and does not require any form of registration.
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.
Finally, for quantitative languages L, L', we study the operations max(L,L'),
min(L,L'), and 1-L as natural generalizations of the boolean operations; we
also consider the sum L + L'. We establish the closure properties of all
classes of quantitative languages with respect to these four operations.
This talk is based on joint work with Krishnendu Chatterjee and Tom
Henzinger.