中科院数学与系统科学研究院
数学研究所
学术报告会
报告人：Prof. Manfred Droste（Universitat Leipzig, Germany)
题 目：Quantitative logics and automata
时 间：10.30（星期四）, 10:00--11:00
地 点：数学院南楼N902室
Abstract：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ützenberger (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üchi, 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.
Biography: Dr. Manfred Droste has been a Professor (C4) at Leipzig University since 2004. He became a member Academia Europaea since 2011. His research interests include Automata theory, logic, algebraic models for concurrent systems, domain theory and model theory, automorphism groups, ordered algebraic structures. He is a program committee member of 34 international conferences. More than 150 research publications in the areas.
附件：