Le séminaire du LSV

Le séminaire du LSV a lieu le mardi à 11h00. Le lieu habituel est la salle de conférences au Pavillon des Jardins (plan d'accès). Pour être informé par email des prochains séminaires, contacter Stéphane Le Roux and Matthias Fuegger.

Le séminaire du LSV est public et ne nécessite aucune inscription préalable.

Séminaires passés

Quantitative Languages: Decision Problems, Expressive Power, and Closure Properties

Visiter le site web pour cet événement | Exporter cet événement au format iCalendar

Date
Le lundi 15 décembre 2008 à 11:00
Lieu
Salle de Conférence (Pavillon des Jardins)
Orateur
Laurent Doyen (École Polytechnique Fédérale de Lausanne)

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.


À propos du LSV

Agenda des séminaires

Exporter l'agenda au format iCalendar | Les séminaires précédents

mar. 19 février

Les séminaires précédents