Logic and Languages

  logicbook Copyright: © Martin Braun

In almost all application areas of logic in computer science, including databases, synthesis, verification, knowledge representation, planning and so on, the aspect of uncertainty plays an enormous and increasing role, see the seminal work of Halpern. The application of formal methods in these areas, often based on the combination of logic with algorithmic methods from automata and game theory, is certainly a success story. It is a major challenge for the further development of such methods to deal with uncertainty and randomness in an adequate way, and to sharpen the mathematical techniques and algorithms for scenarios where incomplete and uncertain data and/or partially observed and random events play a relevant role. The tight relationship between mathematical logic, finite automata, and games which is the basis of many successful formal methods survives also in the context of uncertainty, with game models that become much richer and are closer to reality, with more sophisticated translations between logic, automata and games, and with solution concepts like strategies, equilibria, and so on and algorithms for game models that are more complicated, more difficult to analyse and which require more advanced mathematical techniques. Uncertainty plays an important role in databases too: while the traditional view is that data in a database is correct, nowadays one often has massive amounts of data integrated from different - mostly unreliable web - sources, and there is no hope of „cleaning“ these data. One thus has to cope with uncertain data and adapt both the semantics of and algorithms for query answering. Uncertainties in the input data should therefore be incorporated in the design of databases. The following subsections describe five sample dissertation projects within the research thrust Logic and Languages.