Zajednički sastanak Odeljenja za matematiku i Seminara za logiku, 6. oktobar 2010.

• 30. Septembar,  2010
• Komentari (0)

 Zajednički sastanak Odeljenja za matematiku i Seminara za logiku održaće se 6. oktobra 2010. u 13h u MISANU (Knez Mihailova 36, sprat 3, soba 301f).

Predavač: Manfred Droste, Leipzig University

Naziv predavanja: Weighted automata and quantitative logics

Apstrakt: In automata theory, a classical result of Buchi states that the recognizable languages are precisely the ones definable by sentences of monadic second order logic. We will present a generalization of this result to the context of weighted automata. A weighted automaton is a classical nondeterministic automaton in which each transition carries a weight describing e.g. the resources used for its execution, the length of time needed, or its reliability. The behavior (language) of such a weighted automaton is a function associating to each word the weight of its execution. We develop syntax and semantics of a quantitative logic; the semantics counts 'how often' a formula is true.

Our main results show that if the weights are taken either in an arbitrary semiring or in an arbitrary bounded lattice, then the behaviors of weighted automata are precisely the functions definable by sentences of our quantitative logic. The methods also apply to recent quantitative automata model of Henzinger et al. where weights of paths are determined, e.g., as the average of the weights of the path's transitions. Buchi's result follows by considering the classical Boolean algebra {0,1}.

Joint work with Paul Gastin (ENS Cachan), Heiko Vogler (TU Dresden), resp. Ingmar Meinecke (Leipzig).

---