Deim Seminar
Title
Quantitative Logics and Automata
Conferenciant
Manfred Droste
Professor/a organitzador/a
Josep Domingo-Ferrer
Institution
Universitat de Leipzig
Date
01-10-2012 11:00
Summary
Quantitative models and quantitative analysis in Computer Science
are receiving increased attention. The goal of this talk is to
investigate quantitative automata and quantitative logics.
Weighted automata on finite words have already been investigated
in seminal work of Sch"utzenberger (1961). They consist of classical
finite automata in which the transitions carry weights. These weights
may model, e.g., the cost, the consumption of resources, or the
reliability or probability of the successful execution of the
transitions. This concept soon developed a flourishing theory.
We investigate weighted automata and their relationship to weighted
logics. For this, we present syntax and semantics of a quantitative
logic; the semantics counts 'how often' a formula is true in a given
word. Our main result, extending the classical result of B"uchi, shows
that if the weights are taken from an arbitrary semiring, then weighted
automata and a syntactically defined fragment of our weighted logic are
expressively equivalent. A corresponding result holds for infinite
words. Moreover, this extends to quantitative automata investigated by
Henzinger et al. with (non-semiring) average-type behaviors, or with
discounting or limit average objectives for infinite words.
Place
Laboratori 231
Language
Anglès
