Invited talks
Georg Gottlob
Affiliation: Dept. of Computer Science, University of Oxford, UK Talk title: On the Complexity of Ontological Reasoning under Disjunctive Existential Rules Abstract: Ontology-based data access is an emerging yet powerful technology that allows to enhance a classical relational database with an ontology in order to infer new intensional knowledge. Recently, Datalog+/- was introduced with the purpose of providing tractable reasoning algorithms for expressive ontology languages. In this framework, Datalog is extended by features such as existential quantification in rule heads, and at the same time the rule syntax is restricted to guarantee decidability, and also tractability, of relevant reasoning tasks. We enrich Datalog even more by allowing not only existential quantification but also disjunction in rule heads, and we investigate the complexity of reasoning under the obtained formalism. |
Rolf Niedermeier
Affiliation: Institut fuer Softwaretechnik und Theoretische Informatik, TU Berlin, Germany Talk title: New Races in Parameterized Algorithmics Abstract: Once having classified an NP-hard problem fixed-parameter tractable with respect to a certain parameter, the race for the most efficient fixed-parameter algorithm starts. Herein, the attention usually focuses on improving the running time factor exponential in the considered parameter, and, in case of kernelization algorithms, to improve the bound on the kernel size. Both from a practical as well as a theoretical point of view, however, there are further aspects of efficiency that deserve attention. We discuss several of these aspects and particularly focus on the search for "stronger parameterizations" in developing fixed-parameter algorithms. |
Antonino Salibra
Affiliation: DAIS, Universit? Ca'Foscari Venezia Talk title: Scott is always simple Abstract: We give an outline of recent algebraic results concerning theories and models of the untyped lambda calculus. |
Nicole Schweikardt
Affiliation: Goethe-University Frankfurt am Main, Germany Talk title: A toolkit for proving limitations of the expressive power of logics Abstract: The aim of this talk is to give an overview of recently developed methods for proving limitations of the expressive power of logics. In particular, we shall focus on the following "algebraic" approach that has recently been very successful: The first step is to identify a number of closure properties that the classes of structures defined by sentences of the logic exhibit. The second step is to identify another logic that is characterised by these closure properties. An example of this methodology is a result of Benedikt and Segoufin stating that on successor-based strings, plain first-order logic is as expressive as order-invariant first-order logic. |
Esko Ukkonen
Affiliation: Dept. of Computer Science, University of Helsinki, Finland Talk title: How to Reconstruct a Genome Abstract: Since its early formulations (Peltola et al. 1983), the genome assembly problem has attracted lots of interest from algorithm theoretic as well as from algorithm engineering point of view. In this problem, which is an inversion problem by nature, one is asked to reconstruct the entire DNA sequence from the short, randomly picked sequence fragments that a DNA sequencing instrument is able to read (Myers 1999). With the invent of current high-throughput sequencers producing such fragment reads in massive amounts, there is in molecular biology research a pronounced call for an accurate and fast reconstruction procedure. |
Igor Walukiewicz
Affiliation: LaBRI, CNRS/Universit Bordeaux, France Talk title: Simple models for recursive schemes Abstract: Higher-order recursive schemes are abstract forms of programs where the meaning of built-in constructs is not specified. The semantics of a scheme is an infinite tree labeled with built-in constructs. The research on recursive schemes spans over more than forty years. Still, central problems like the equality problem, and more recently, the model checking problem for schemes remain very intriguing. Even though recursive schemes were originally though of as a syntactic simplification of a fragment of the lambda calculus, we propose to go back to lambda calculus to study schemes. In particular, for the model checking problem we propose to use standard finitary models for the simply-typed lambda calculus. |
Gerhard J. Woeginger
Affiliation: Dept. of Mathematics and Computer Science, TU Eindhoven, Netherlands Talk title: Transportation under nasty side constraints Abstract: The talk discusses planning problems where a set of items has to be transported from location A to location B subject to certain collision and/or resource constraints. We analyze the behavior of these problems, discuss their history, and derive some of their combinatorial and algorithmic properties. |
Mihalis Yannakakis
Affiliation: Dept. of Computer Science, Columbia University, USA Talk title: Computation of Least Fixed Points Abstract: Many problems from different areas can be formulated as problems of computing a fixed point of a suitable function. Classical examples include the computation of equilibria for games, price equilibria for markets, and many others. For many of those problems, the function in the fixed point formulation is monotone, and the objects we want to compute are given by a specific fixed point, namely the least fixed point of the function. Many models and problems from a broad variety of areas can be thus expressed as least fixed point computation problems, including in particular the analysis of various probabilistic models, problems in stochastic optimization, and games. It turns out that for some classes of functions we can compute the least fixed point in polynomial time and thus we can analyze efficiently several of these models, while for others there are strong indications that they cannot be solved in polynomial time, and for yet others the question remains open. In this talk we will discuss progress in this area. The talk is based on a series of works with Kousha Etessami and Alistair Stewart. |