This talk reports about the results achieved so far in the context of a research programme at the cutting point of logic, formal language theory, and complexity theory. The aim of this research programme is to classify the complexity of evaluating formulas from different prefix classes of second-order logic over diferent types of finite structures, such as strings, graphs, or arbitrary structures. In particular, we report on classifications of second-order logic on strings and of existential second-order logic on graphs.
Georg Gottlob is a Professor of Computer Science at the Technical University of Vienna, Austria, where he currently leads the Database and AI group. His research interests are database theory (in particular, query languages), Web information processing, constraint satisfaction problems, nonmonotonic reasoning, finite model theory, and computational complexity. On the more applied side, he supervises a number of industry projects dealing with expert systems and with multimedia information systems. From 1989 to 1996 he directed the industry-funded Christian Doppler Laboratory for Expert Systems. He is a co-founder of the Lixto Corporation. Gottlob got his Engineer and Ph.D. degrees in Computer Science from TU Vienna, Austria in 1979 and 1981, respectively. He holds his current position since 1988. Before that, he was affiliated with the Italian National Research Council in Genoa, Italy, and with the Politecnico di Milano, Italy. During the spring semester 1999 he was invited McKay Professor at UC Berkeley. Georg Gottlob was an invited speaker at many international conferences. He received the Wittgenstein Award from the Austrian National Science Fund and was elected corresponding Member of the Austrian Academy of Sciences. He recently chaired the Program Committee of ACM PODS 2000 and was Program Chair of IJCAI 2003.
Sprecher: Prof. Dr. Georg Gottlob Wann: Freitag, 1. April 2005, 15:00 Uhr (s.t.), E.1.42 Wo: Universität Klagenfurt