Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
  • Zielgruppen
  • Suche

Prof. Dr. Christina Brzuska, TU Hamburg-Harburg

Assumptions in Cryptography – Do., 26.05.16, 10.15h, Raum 224, Appelstr. 4

If P=NP, virtually all cryptographic primitives (in particular symmetric-key encryption where the messages are longer than the key and public-key encryption) do not exist. As there is little hope that within our lifetime, one will prove that P is not equal to NP, the cryptographic community needs to rely on assumptions, and not surprisingly, cryptographic assumptions are an important area of research in cryptography.

If we need to assume that P is not equal to NP is a necessary assumption for cryptography, then it would be most desirable to show that this assumption also suffices. Unfortunately, no results of this type are known and I will spend most of my talk explaining the difficulty of proving such a statement.

If time permits (depending on the number of questions during the talk), I will then discuss indistinguishability obfuscation (iO) which is a fairly new cryptographic primitive that does not really "fit" with our existing conceptual frameworks. In particular, unlike all other non-trivial cryptography, if P=NP, then iO exists. Yet, iO is a very strong primitive that allows for a lot of "fancy" applications and is even mutually exclusive with other cryptographic assumptions.

Dr. Sebastian Ordyniak, TU Wien

Backdoors into Heterogeneous Classes of SAT and CSP – Do., 10.12.15, 13.30h, Raum 224, Appelstr. 4

In this work we extend the classical notion of strong and weak backdoor sets by allowing that different instantiations of the backdoor variables result in instances that belong to different base classes; the union of the base classes forms a heterogeneous base class. Backdoor sets to heterogeneous base classes can be much smaller than backdoor sets to homogeneous ones, hence they are much more desirable but possibly harder to find. We draw a detailed complexity landscape for the problem of detecting strong and weak backdoor sets into heterogeneous base classes for SAT and CSP.

Dr. Sebastian Ordyniak, TU Wien

Parameterized Algorithms for Parity Games – Di., 08.12.15, 15.15h, Raum 235, Appelstr. 4

Determining the winner of a Parity Game is a major problem in computational complexity with a number of applications in verification. In a parameterized complexity setting, the problem has often been considered with parameters such as (directed versions of) treewidth or clique-width, by applying dynamic programming techniques.

In this talk we show how to adopt a parameterized approach which is more inspired by well-known (non-parameterized) algorithms for this problem. We consider a number of natural parameterizations, such as by Directed Feedback Vertex Set, Distance to Tournament, and Modular Width. We show that, for these parameters, it is possible to obtain recursive parameterized algorithms which are simpler, faster and only require polynomial space. We complement these results with some algorithmic lower bounds which, among others, rule out a possible avenue for improving the best-known sub-exponential time algorithm for parity games.

Dr. Johannes Fichte, TU Wien

Backdoors to Tractability of Disjunctive Answer Set Programming – Do., 19.11.15, 11.00h, Raum 235, Appelstr. 4

Answer set programming (Asp) is an increasingly popular framework for declarative programming that admits the description of problems by means of atoms, rules, and constraints that form a logic program. The solutions of an answer set program are called answer sets. Many problems in artificial intelligence such as non-monotonic reasoning can be directly formulated in Asp. Reasoning problems for propositional disjunctive programs, which is the focus of this thesis, are of high computational complexity. For instance, the problems of deciding whether a program has at least one answer set or whether a given atom is contained in at least one answer set, are complete for the second level of the Polynomial Hierarchy.

In this thesis we tackle these hard problems using backdoors in problem instances, which are sets of atoms that can be used as clever reasoning shortcuts through the search space. The concept of backdoors has widely been used in theoretical investigations in the areas of propositional satisfiability and constraint satisfaction, we show that backdoors can be fruitfully adapted to Asp.

We develop a rigorous theory of backdoors for Asp and carry out a fine-grained asymptotic computational complexity analysis that takes backdoors into account. We establish new algorithms that can detect and take advantage of small backdoors to solve or to significantly simplify problem instances. More precisely, certain back- doors allow us to solve Asp reasoning problems efficiently for instances with small backdoors (fixed-parameter tractability), other backdoors allow us to significantly simplify the problem instance (complexity barrier breaking reduction), and some backdoors cannot even be used to simplify the problem instance (intractability). Particularly, our simplifications break the complexity barrier between the second level of the Polynomial Hierarchy and the first level by means of reductions that work efficiently for instances with small backdoors. Further, we elaborate upon a detailed comparison where we compare the size of certain types of backdoors with each other. We show that backdoors can serve as a unifying framework for restrictions that have been identified in the literature under which Asp problems significantly simplify and become tractable or NP-complete. 

Dr. Thomas Schneider, Universität Bremen
Lightweight Description Logics & Branching Time: A Troublesome Marriage - Do., 26.03.2015, 14.00h, Raum 224, Appelstr. 4
We study branching-time temporal description logics (BTDLs) based on the temporal logic CTL in the presence of rigid (time-invariant) roles and general TBoxes. There is evidence that, if full CTL is combined with the classical description logic ALC in this way, reasoning becomes undecidable. In this paper, we begin by substantiating this claim, establishing undecidability for a fragment of this combination. In view of this negative result, we then investigate BTDLs that emerge from combining fragments of CTL with lightweight description logics from the EL and DL-Lite families. We show that even rather inexpressive BTDLs based on EL exhibit very high complexity. Most notably, we identify two convex fragments which are undecidable and hard for non-elementary time, respectively. For BTDLs based on DL-Lite_N^bool, we obtain tight complexity bounds that range from PSPACE to EXPTIME.   Joint work with Víctor Gutiérrez-Basulto and Jean Christoph Jung.  
Dr. Andreas Krebs, Universität Tübingen
Visibly Counter Languages and Constant Depth Circuits - Do., 29.01.2015, 13.15h, Raum 224, Appelstr. 4
We examine visibly counter languages, which are languages recognized by visibly counter automata (a.k.a. input driven counter automata). We are able to effectively characterize the visibly counter languages in AC0 and show that they are contained in FO[+].  
Dr. Wojtek Jamroga, Polish Academy of Sciences
Defendable Security in Interaction Protocols - Di., 07.10.2014, 11.00h, Raum 224, Appelstr. 4
We study the security of interaction protocols when incentives of participants are taken into account. We begin by formally defining correctness of a protocol, given a notion of rationality and utilities of participating agents. Based on that, we propose how to assess security when the precise incentives are unknown. Then, the security level can be defined in terms of defender sets, i.e., sets of participants who can effectively “defend” the security property as long as they are in favor of the property. In terms of technical results, we present a theoretical characterization of defendable protocols under Nash equilibrium, and study the computational complexity of related decision problems.   The talk reports joint work with Matthijs Melissen and Henning Schnoor.
Prof. Tanka Nath Dhamala, Tribhuvan University, Nepal
Contraflow Approach for Evacuation Planning Network Optimization Algorithms - Do., 15.05.2013, 13.00h, Raum 023, Appelstr. 4
The dynamic network optimization solutions have quite large range of applications in emergency evacuation, network communication and scheduling, logistics, transportation and dynamic assignment. Among a variety of dynamic flow models covering from variational inequality to nonlinear non-convex programming, macroscopic and microscopic models and integrated model for discrete as well as continuous time flows based on measure theory, we consider the network flow model in discrete settings. The capability of reversing arcs in a given network significantly improves the result quality; however, even basic problems in this class are computationally hard. Although, many experiments have been implemented based in this approach, theoretical guarantees have rarely been presented. We consider the contraflow model, present an efficient algorithm and prove its validity for particular class of networks.
Prof. Dr. Andreas Winter, Carl von Ossietzky Universität Oldenburg
Improving Energy Efficiency by Model-Driven Software Reengineering - Mo., 28.01.2013, 15.00h, Raum 027, Appelstr. 4
More and more mobile computing devices, like cell phones and tablets, are used today. Whereas plenty of effort was and is spent on optimizing energy efficiency of mobile devices on a hardware and operating system level, activities on analyzing and optimizing applications on a code basis is still in its infancy. In this presentation, we show the application of model driven reengineering techniques to evaluate and to affect the energy consumption of software applications on code level. The idea of Energy Code Smells is presented. Energy wasteful code is detected according to code anti-patterns and structured transformations provide code improvements. These model-driven techniques to identify and resolve energy code smells rely on graph-based software analysis techniques.
Prof. Tanka Nath Dhamala, Tribhuvan University, Nepal
An efficient algorithm for mixed-model just-in-time production with a genreralized perspective. - Mi., 30.05.2012, 10.00h, Raum 023, Appelstr. 4
The problem of penalizing jobs both for being tardy and for being early has been considered as one of the fertile research topics in operations research. We consider just-in-time mixed-model production sequencing problems with batching and without batching. They are modeled with the elegant concept of balanced words, graph theory and optimization techniques. The output rate variation problem is very challenging from computational point of view. The product rate variation problem minimizes the variation in the rate at which different models are produced. They have mathematically interesting base models with theoretical value as well as real world applications like real-time scheduling, response time variability, networking and apportionment problem. The problem of minimizing deviations between actual and desired production for single-level can be solved efficiently. The cyclic sequences are optimal for single-level problem reducing the complexity. In this talk, we mainly deal with the bottleneck product rate variation problem and its solution procedure. We also discuss this problem with a given set of sequences as precedence constraints.
Prof. Dr. Ulrich Hertrampf, Univ. Stuttgart
Ein kombinatorischer Beweis für ein altes Resultat von Trakhtenbrot - Mo., 27.02.2012, 11.00h, Raum 224, Appelstr. 4
Boris Trakhtenbrot hat 1963 einen topologischen Beweis veröffentlicht für den Satz, dass (m,n)-berechenbare Funktionen im Fall m > n/2 bereits im üblichen Sinn berechenbar sind. Eine Funktion f heißt hierbei (m,n)-berechenbar, wenn es einen Algorithmus gibt, der auf n verschiedene Eingaben x_1,...,x_n nach endlicher Zeit mit n Ausgaben y_1,...,y_n stoppt und die Bedingung y_i=f(x_i) für mindestens m der Indizes i=1,...,n erfüllt. Im Vortrag werde ich den wesentlich einfacheren (kombinatorischen) Beweis von Austinat, Diekert, Hertrampf, Petersen (TCS 330, 2005) vorstellen, der den zusätzlichen Vorteil hat, dass er auf das Modell endlicher Automaten übertragbar ist.
Dr. Conrad Drescher, Univ. Oxford
The Partner Units Problem - Do., 21.02.2012, 11.00h, Raum 224, Appelstr. 4
The Partner Units Problem is a graph partitioning problem with applications in surveillance and traffic monitoring. In this talk we present general problem properties, a polynomial algorithm for a practically important subclass of instances and techniques for modelling the problem as a satisfiability or constraint satisfaction problem.
Dr. Andreas Krebs, Univ. Tübingen
Non-definability of languages by generalized first-order formulas over (N,+) - Do., 16.02.2012, 11.00h, Raum 224, Appelstr. 4
We consider first-order logic with monoidal quantifiers over words. We show that all languages with a neutral letter, definable using the addition numerical predicate are also definable with the order predicate as the only numerical predicate. Let S be a subset of monoids. Let LS be the logic closed under quantification over the monoids in S and N be the class of neutral letter languages. Then we show that: LS[<,+] cap N = LS[<] Our result can be interpreted as the Crane Beach conjecture to hold for the logic LS[<,+]. As a corollary of our result we get the result of Roy and Straubing that FO+MOD[<,+] collapses to FO+MOD[<]. For cyclic groups, we answer an open question of Roy and Straubing, proving that MOD[<,+] collapses to MOD[<]. Our result also shows that multiplication is necessary for Barrington's theorem to hold. All these results can be viewed as separation results for very uniform circuit classes. For example we separate FO[<,+]-uniform CC0 from FO[<,+]-uniform ACC0.
Dr. Beate Bollig, TU Dortmund
Implizite Algorithmen für Matchingprobleme - Do., 26.01.2012, 14.00h, Raum 224, Appelstr. 4
Binäre Entscheidungsdiagramme (Binary Decision Diagrams), werden als Berechnungsmodell in der Komplexitätstheorie seit langem untersucht, um Zusammenhänge zwischen Speicherplatz- und Rechenzeitverbrauch diskreter Probleme abzuschätzen. Eingeschränkte Varianten wie OBDDs haben sich in vielen Anwendungen als Datenstruktur für Boole'sche Funktionen durchgesetzt und spielen seit einiger Zeit auch eine Rolle in der Algorithmik großer und komplexer Netzwerke. Reichen Rechenzeit oder Speicherplatz nicht mehr aus, um jeden Eingabeknoten individuell zu betrachten, kann die Verarbeitung von Knoten- und Kantenmengen, die mittels ihrer charakteristischen Funktionen repräsentiert werden, einen möglichen Ausweg bieten. Graphprobleme müssen in diesem Fall mit Hilfe funktionaler Operationen auf diesen Funktionen gelöst werden. Nach einer Einführung in den Entwurf und die Analyse impliziter OBDD-basierter Graphalgorithmen, werden in diesem Vortrag effiziente Algorithmen für Matchingprobleme vorgestellt, erste hoffnungsvolle experimentelle Ergebnisse präsentiert, jedoch auch Grenzen der Machbarkeit aufgezeigt.
Dr. Thomas Schneider, University of Bremen
The Complexity of Monotone Hybrid Logics over Linear Frames and the Natural Numbers - Di., 24.01.2012, 13.30h, Raum 027, Appelstr. 4
Hybrid logic (HL) with binders is an expressive specification language that extends modal logic. Its satisfiability problem is undecidable in general. To represent the temporal behavior of systems and agents, structures over which ML and HL are interpreted can be restricted to the natural numbers or general linear orders. Over both these frame classes, satisfiability of HL with binders is known to be decidable, but of non-elementary complexity. In this talk, we consider monotone HLs (i.e., the Boolean connectives are conjunction and disjunction only) over the natural numbers and general linear orders. We show that the satisfiability problem remains non- elementary over linear orders, but its complexity drops to PSPACE- completeness over natural numbers. We categorize the strict fragments arising from different combinations of modal and hybrid operators into NP-complete and tractable, and show that the latter cases are complete for NC1 or LOGSPACE. Interestingly, NP-completeness depends only on the fragment and not on the frame. For the cases above NP, satisfiability over linear orders is harder than over natural numbers, while below NP it is at most as hard. In addition to the study of computational complexity, we examine model-theoretic properties of the fragments in question. This is joint work with Stefan Goeller (Bremen), Arne Meier (Hannover), Martin Mundhenk (Jena), Michael Thomas (TWT GmbH) and Felix Weiss (Jena).
Prof. Dr. Carsten Lutz, Univ. Bremen
Non-Uniform Data Complexity in Ontology-Based Data Access with Description Logics. - Do., 15.12.2011, 14.00h, Raum 224, Appelstr. 4
In recent years, the use of ontologies to access instance data has become increasingly popular. The general idea is that an ontology (a logical theory) gives a semantics to the predicates used in the database, thus allowing more complete answers to queries, enriching the vocabulary available for querying, and facilitating translation when the data vocabulary and the query vocabulary are different. In this presentation, I will focus on ontologies formulated in description logics (DLs) and advocate a novel approach to studying the data complexity of query answering w.r.t. DL ontologies. This approach is non-uniform in the sense that individual ontologies are considered instead of all ontologies that can be formulated in a given DL. It allows us to ask rather fine-grained questions about the data complexity of DLs, such as: given a DL L, how can one characterize the ontologies for which query answering is in PTime or FO-rewritable? Is there a dichotomy between being in PTime and being coNP-hard? We provide several answers to such questions, some of which are based on a novel connection between query answering w.r.t. DL ontologies and constraint satisfaction problems (CSPs) that allows us to transfer various results from CSPs to DLs. We also identify a class of ontologies within the expressive DL ALCFI that enjoy PTime data complexity; the new class strictly extends the Horn fragment of ALCFI, which was was the largest known tractable fragment of ALCFI so far.
Prof. Dr. Friedrich Otto, Universität Kassel
On Cooperating Distributed Systems of Stateless Deterministic Restarting Automata with Window Size One - Mi., 06.07.2011, 14.00h, Raum 335, Appelstr. 4
The restarting automaton is a machine model that is motivated by the technique of analysis by reduction from linguistics. It consists of a finite-state control and a flexible type with end markers and a read/write window of a fixed size. This talk focuses on the weakest model of the restarting automaton: the so-called R-automaton with a read/write window of size one (R(1)-automaton for short). It is well-known that R(1)-automata accept exactly the regular languages, while stateless deterministic R(1)-automata just accept regular languages of a very restricted form. Accordingly we combine a finite number of such automata into a cooperating distributed system (CD-system) of stateless deterministic R(1)-automata. These CD-systems only accept languages with semi-linear Parikh images, but they turn out to be quite powerful, as they accept all rational trace languages. In fact, the rational trace languages (and even the context-free trace languages) can been characterized in terms of certain CD-systems of stateless deterministic R(1)-automata. If the components of these CD-system are not required to be stateless, then these systems are strictly more expressive, as then they even accept some languages that are not semi-linear.
Kord Eickmeyer, Humboldt-Universität zu Berlin
Randomisation and Derandomisation in Descriptive Complexity Theory - Mi., 18.05.2011, 13.30h, Raum 224, Appelstr. 4
We study randomised complexity classes, in particular randomised AC0 under various uniformity conditions, using tools from descriptive complexity theory. To this end, we introduce randomised logics and study their expressive power. Using tools from finite model theory, we were able to show that randomised first-order logic provably gains expressive power, even on structures with an addition relation. In complexity theory terms, this implies that under a certain strict uniformity condition, BPAC0 cannot be derandomised. Furthermore, we show that on certain restricted classes of structures, randomised first-order logic can in fact be derandomised. The proof is of interest as it deviates from the standard schema of constructing a pseudorandom generator from hard functions.
Christoph Berkholz, Humboldt-Universität zu Berlin
Über die Schaltkreiskomplexität parametrisierter Probleme - Do., 05.05.2011, 14.00h, Raum 224, Appelstr. 4
In diesem Vortrag zeigen wir obere und untere Schranken für parametrisierte Probleme innerhalb der Schaltkreiskomplexitätsklasse AC^0. Als erstes Ergebnis in diese Richtung bewies Benjamin Rossman 2007, dass k-Clique (enthält ein gegebener Graph eine Clique der Größe k?) AC^0-Schaltkreise der Größe n^{2k/9} benötigt. Kazuyuki Amano konnte 2009 die Methode auf Subgraphisomorphieprobleme erweitern. Darauf aufbauend zeigen wir untere Schranken für induzierte Subgraphisomorphie- und Homomorphieprobleme. Mit einer auf Schaltkreise übertragenen fpt-Reduktion folgt, dass die k-Clique-Schranke auch für das W[2]-vollständige k-DominatingSet gilt. Auf der anderen Seite können wir zeigen, dass sich das parametrisch leichte k-VertexCover mit f(k)n^2 Gattern in AC^0 berechnen lässt.
Prof. Dr. Lauri Hella, University of Tampere, Finland
Partially ordered connectives and monadic monotone strict NP - Mi., 23.06.2010, 14.30h, Raum 027, Appelstr. 4
In this paper we investigate the complexity of abduction, a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining how the world behaves it aims at finding an explanation for some observed manifestation. In this paper we consider propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to be SigmaPtwo-complete in general. We focus on formulae in which the allowed connectives are taken from certain sets of Boolean functions. We consider different variants of the abduction problem in restricting both the manifestations and the hypotheses. For all these variants we obtain a complexity classification for all considerable sets of Boolean functions. In this way, we identify easier cases, namely NP-complete, coNP-complete and polynomial cases. Thus, we get a detailed picture of the complexity of the propositional abduction problem, hence highlighting sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.
Johannes Schmidt, LIF Marseille
Complexity classifications for Propositional Abduction in Post's framework - Do., 20.05.2010, 15.00h, Raum 224, Appelstr. 4
In this paper we investigate the complexity of abduction, a fundamental and important form of non-monotonic reasoning. Given a knowledge base explaining how the world behaves it aims at finding an explanation for some observed manifestation. In this paper we consider propositional abduction, where the knowledge base and the manifestation are represented by propositional formulae. The problem of deciding whether there exists an explanation has been shown to be SigmaPtwo-complete in general. We focus on formulae in which the allowed connectives are taken from certain sets of Boolean functions. We consider different variants of the abduction problem in restricting both the manifestations and the hypotheses. For all these variants we obtain a complexity classification for all considerable sets of Boolean functions. In this way, we identify easier cases, namely NP-complete, coNP-complete and polynomial cases. Thus, we get a detailed picture of the complexity of the propositional abduction problem, hence highlighting sources of intractability. Further, we address the problem of counting the explanations and draw a complete picture for the counting complexity.
Thomas Zeume, TU Dortmund
Two-Variable Logic with Two Order Relations - Do., 20.05.2010, 14.15h, Raum 224, Appelstr. 4
The finite satisfiability problem for two-variable logic over structures with unary relations and two order relations is investigated. Firstly, decidability is shown for structures with one total preorder relation and one linear order relation. More specifically, we show that this problem is complete for EXPSPACE. As a consequence, the same upper bound applies to the case of two linear orders. Secondly, we prove undecidability for structures with two total preorder relations as well as for structures with one total preorder and two linear order relations. Further, we point out connections to other logics. Decidability is shown for two-variable logic on data words with orders on both positions and data values, but without a successor relation. We also study “partial models” of compass and interval temporal logic and prove decidability for some of their fragments.
Dr. Sven Kosub, Universität Konstanz
Algorithmische Analyse diskreter Netzwerkdynamiken - Mo., 26.04.2010, 14.15h, Raum 027, Appelstr. 4
Viele Funktionalitäten komplexer Netzwerke konstituieren sich in einem dynamischen Prozess. Solche Funktionalitäten aus lokal beobachtbaren strukturellen Netzwerkeigenschaften heraus zu analysieren und zu kontrollieren, ist eine zentrale Zielstellung bei der Handhabung komplexer Systeme. Während für die Analyse von Netzwerkdynamiken mit kontinuierlicher Zeit durch der Behandlung von Differentialgleichungssystemen eine einheitliche, mächtige algorithmische Methodik zur Verfügung steht, ist dies für diskrete Netzwerkdynamiken (vor allem bei nicht-technischen Systemen) nicht in hinreichendem Maße der Fall.
In diesem Vortrag werden wir diesbezüglich Klassen endlicher, diskreter dynamischer Systeme und ihre algorithmischen Eigenschaften, insbesondere hinsichtlich der Existenz von Fixpunkten, in einem einheitlichen Rahmen diskutieren. Der diskrete Ensembleansatz in der Systembiologie steht dabei vor allem im Zentrum des Interesses.
Dr. Thomas Schneider, University of Manchester
Modularity of Ontologies - Di., 25.03.2010, 15.00h, Raum 224, Appelstr. 4
As more and more large, complex OWL ontologies become available on the Web, the need for mechanisms and methodologies for managing them becomes more urgent. Description logics, such as those underlying the W3C-recommended Web Ontology Language OWL, traditionally have not had many features for "development in the large", much less for topic analysis and extraction services so valuable for large scale development or for cross-organisational, uncoordinated reuse. Fortunately, there have been a number of impressive advances in our understanding of how to analyse the modular structure of ontologies.
This talk will provide an introduction to module-oriented development of OWL ontologies. We will give three distinct scenarios where modules are useful, namely reuse, collaborative development, and understanding of ontologies. Focussing on the first scenario, we will describe the logical background, compare different module extraction approaches, and outline the current tool support. Finally we will show how modules can contribute to understanding ontologies---a research area in progress.
Thomas Schneider is a post-doctoral Research Associate in the School of Computer Science at the University of Manchester. He is working in the EPSRC-funded project "Composing and decomposing ontologies: a logic-based approach". This talk will report on research jointly carried out with Bijan Parsia and Uli Sattler.
Dr. Raghavendra Rao B. V., Chennai Mathematical Institute
Small space analogues of Valiant's classes - Di., Am 16.2.10, 10.30h, Raum 224, Appelstr. 4
The width of a boolean circuit exactly characterises the "space" complexity of the computed function in the uniform circuit model of computation. In this talk we study an algebraic variant of this relationship.
We propose the width of an arithmetic circuit as a possible measure of space and introduce the class VL as an algebraic variant of deterministic log-space DLOG. In the uniform setting, we show that our definition coincides with that of VPSPACE at polynomial width.
Further, to define algebraic variants of non-deterministic space-bounded classes, we introduce the notion of ``read-once'' certificates for arithmetic circuits. We show that polynomial-size algebraic branching programs can be expressed as a read-once exponential sum over polynomials in VL. We also show that the class of algebraic branching programs are stable under read-once exponential sums. We will also discuss some improved upper bounds for the read-once exponential sums of certain classes of width bounded arithmetic circuits.
Dr. Jochen Messner, FH Aalen
Nichtdeterministische Funktionen, disjunkte Paare und optimale Beweissysteme - Di., 15.09.2009, 14.00h, Raum 224, Appelstr. 4
Wir zeigen zunächst, dass die nichtdeterministischen Funktionenklassen NPSV und NPMV_t eng mit den Klassen disjunkter Paare DisjNP bzw. DisjCoNP zusammenhängen. Dann untersuchen wir die Frage, ob optimale Beweissysteme für TAUT bzw. p-optimale Beweissysteme für SAT existieren und zeigen, dass eine positiven Antwort auf diese Frage vollständige Funktionen bzw. Paare für diese Klassen impliziert. Die Annahme, dass das übliche Beweissystem für SAT (Beweis durch Angabe einer erfüllenden Belegung) p-optimal ist, impliziert sogar den Kollaps von NPMV_t auf FP. Andererseits impliziert die gegenteilige Annahme, dass die Suche nach einer erfüllenden Belegung für viele Formeln wesentlich schwieriger ist, als zu erkennen, dass die Formeln erfüllbar sind. Die Annahme, dass ein optimales Beweissystem für TAUT existiert, das effektive Interpolation erlaubt, führt dagegen zu einem Kollaps von NPSV auf FP/poly.
Prof. Friedrich Steimann, Universität Hagen
Constraint-basierte Refaktorisierung am Beispiel der Änderung von Sichtbarkeiten - Mo., 15.06.2009, 16.15h, Raum 027, Appelstr. 4
Unter Refaktorisierung versteht man die bedeutungserhaltende Änderung von Software. Viele gängige Entwicklungsumgebungen enthalten heute Refaktorisierungswerkzeuge, mit denen sich beispielsweise Programmelemente konsistent umbenennen oder verschieben lassen. Solche Programmänderungen sind nur scheinbar trivial und so kommt es, daß praktisch alle Refaktorisierungswerkzeuge heute fehlerbehaftet sind. In dem Vortrag wird gezeigt, wie sich der Spielraum für Refaktorisierungen mittels Constraints darstellen läßt, die vor einer Refaktorisierung aus einem Programm gewonnen werden. Als Beispielanwendung werden dafür die Sichtbarkeitsregeln von Java herangezogen, die beim Verschieben von Programmelementen eine wichtige Rolle spielen.
Dr. Wojtek Jamroga, TU Clausthal
Easy Yet Hard. Model Checking Strategies of Agents - Mo., 20.4.2009, 13.15h, Raum 224, Appelstr. 4  
I present an overview of complexity results for model checking of temporal and strategic logics. It turns out that it is possible to manipulate the context so that different complexity results are obtained for the same problem. Among other things, this means that the results are often distant from the "practical" complexity which is encountered when one tries to use the formalisms in reality.  


Dr. Juha Kontinen, Helsingin Yliopisto 
Dependence logic - Di, 10.3.2009, 16.00h, Raum 224 (Appelstr. 4) 
In this talk we discuss Dependence logic which incorporates the concept of dependence into first-order logic. We give the syntax and semantics of dependence logic and dicuss its basic properties. We also show that, in expressive power, dependence logic coincides with that of existential second-order logic.

The main reference for the talk is the book by professor Jouko Väänänen: Dependence Logic: A New Approach to Independence Friendly Logic, London Mathematical Society Student Texts (No. 70) Cambridge University Press, 2007. 


Dr. Oliver Kutz, Universität Bremen 
Heterogeneously Structured Ontologies ‒ Do, 29.1.2009, 13.30h, Raum 224 (Appelstr. 4) 
Ontologies play an increasingly important role in various areas of Knowledge Representation ranging from the life sciences and engineering domains to linguistic semantics. In the process, ontologies are being designed in a broad spectrum of logics, with considerably varying expressivity and supporting quite different reasoning methods. Logics being used include description logics like SROIQ(D) (underlying the Web Ontology Language OWL-DL 2.0), relational database schemes, as well as first-order and modal logics. While aligning and re-using (parts of) ontologies has received considerable attention recently, there is little work on formal structuring and the aspect of heterogeneity.
We believe that a lot can be learned in this respect from techniques developed for (algebraic) specification in software engineering, and provide a systematic account that parallels structuring techniques from algebraic specification with typical ontology structuring problems and design tasks found in ontology engineering.
In the talk, we will briefly introduce theoretical background, including institution theory and development graphs. We then employ the heterogeneous structuring mechanisms of the heterogeneous algebraic specification language HetCASL for defining an abstract notion of structured heterogeneous ontology, and show how this allows to split up a heterogeneous ontology into semantically meaningful parts and employ dedicated reasoning tools to them.
In particular, we will distinguish three fundamentally different kinds of combining heterogeneous ontologies: integration, connection, and refinement, and discuss corresponding applications, namely modular reasoning, consistency through modular model construction, and heterogeneous refinements of the foundational ontology DOLCE. We will also give a brief demonstration of the heterogeneous reasoning system HETS that is being developed at the University of Bremen. 


Dipl.-Inform. Volker Weber, TU Dortmund 
Branching-Time Logics Repeatedly Referring to States ‒ 29. September 2008, 11.00 Uhr, Raum 224, Appelstraße 4 
While classical temporal logics lose track of a state as soon as a temporal operator is applied, several branching-time logics able to repeatedly refer to a state have been introduced in the literature.
We study such logics by introducing a new formalism, hybrid branching-time logics, subsuming the other approaches and making the ability to refer to a state more explicit by assigning a name to it.
We analyze the expressive power of hybrid branching-time logics and the complexity of their satisfiability problem. As main result, the satisfiability problem for the hybrid versions of several branching-time logics is proved to be 2EXPTIME-complete.
A common property of the logics studied is that they refer to only one state. This restriction is crucial: The ability to refer to more than one state causes a nonelementary blow-up in complexity. In particular, we prove that satisfiability for NCTL* has nonelementary complexity. 


Dr. Wojtek Jamroga, TU Clausthal 
A Logic for for Reasoning about Rational Agents ‒ 23. Januar 2008, 11.15 Uhr, Raum 224, Appelstraße 4 
We propose an extension of alternating-time temporal logic that can be used for reasoning about the behavior and abilities of agents under various rationality assumptions (e.g., that only Nash equilibria can be played). We also present some characterizations of game-theoretical solution concepts, and discuss the notion of qualitative solution concept, based on winning conditions defined by temporal path formulae. 


Dr. WojtekProf. Dr. Pierre McKenzie, Université de Montréal  Jamroga, TU Clausthal
The complexity of Solitaire ‒ 05. Juni 2007, 16.15 Uhr, Raum 224, Appelstraße 4 
Klondike solitaire is the well-known "patience" card game available on most personal computers. After a few words on the history of the game, we'll analyse the complexity of determining whether an initial configuration of n cards can lead to a win in this game (can you guess the answer?). Then we'll consider some variants of the game. 


Prof. Dr. Martin Otto, TU Darmstadt 
Bisimulation, Games and Modal Logics ‒ 23. Mai 2007, 16.15 Uhr, Raum 224, Appelstraße 4 
Modal logics - and their extensions to guarded logics provide useful tractable fragments of first-order logic whose expressiveness is closely matched to bisimulation equivalences between structures. Key model theoretic properties of modal and guarded fragments can be understood in terms of corresponding bisimulation games and model constructions adapted to these. With some slightly more intricate combinatorics, some such constructions can be made to work for finite models or over other interesting non-elementary classes of structures. 


Dr. Juha Kontinen, Helsingin Yliopisto 
Majority in logic and computation ‒ 24. April 2007, 16.15 Uhr, Raum 224, Appelstraße 4 
The topic of the talk is descriptive complexity theory. The logarithmic, linear, and polynomial hierarchy have been characterized logically in terms of alternating universal and existential quantifiers. In this talk we consider the so-called counting extensions of these hierarchies. We show that these classes can be analogously characterized in terms of majority quantifiers. 


Prof. Dr. Pierre McKenzie, Université de Montréal, 
Incremental branching programs ‒ 16. November 2006, 15.00 Uhr, Raum 224, Appelstraße 4 
After reviewing the connection between Turing machines and branching programs, we will introduce a new model of restricted branching programs which we call incremental branching programs. We will sketch the argument that syntactic incremental branching programs capture previously studied structured models of computation for the P-complete problem GEN and for a natural NL-complete restriction, namely marking machines and Poon's extension of jumping automata on graphs. This connection yields exponential size lower bounds for syntactic incremental branching programs for GEN. We will then discuss the improvements that would be required in order to separate major complexity classes such as Logspace and P. 


Prof. Dr. Stephan Waack, Universität Göttingen, 
Erkennung genomischer Inseln mit Hidden-Markow-Modellen ‒ 10. Juli 2006, 16.00 Uhr, Raum 027, Appelstraße 4 
Horizontaler Gentransfer zwischen Spezies mit teilweise sehr geringem Verwandtschaftsgrad gilt gegenwärtig als ein Motor der Evolution in der Welt der Prokaryoten (Wesen ohne Zellkern). Häufig haben solche von Art zu Art transferierten DNA-Stücke eine beträchtliche Länge und werden deshalb als genomische Inseln (GI) bezeichnet. Molekularbiologen haben ein großes Interesse an Algorithmen, die GI erkennen.
Nach einer Einführung in die biologische Problematik und einer allgemeinen Vorstellung von Hidden-Markow-Modellen werden in dem Vortrag die Methoden, auf deren Grundlage unser Program SIGI-HMM fremde Gene vorhersagt, dargestellt. Abschließend wird die Auswertung verschiedener Genome durch das Göttinger Genomik Labor (G2L) unter Verwendung von SIGI-HMM beschrieben. 


Prof. Dr. Martin Grohe, Humboldt-Universität zu Berlin, 
Räuber, Gendarmen und die Struktur effizient lösbarer Constraint-Satisfaction-Probleme ‒ 24. April 2006, 16.00 Uhr, Raum 135, Appelstraße 4 
Constraint-Satisfaction-Probleme (CSP) bilden eine natürliche Klasse von algorithmischen Problemen, die wichtige Anwendungen in ganz verschiedenen Bereichen wie künstliche Intelligenz, Datenbanken, automatische Verifikation und statistische Physik haben. Prominentestes Beispiel eines CSP ist das aussagenlogische Erfüllbarkeitsproblem.
Im Allgemeinen sind CSP schwer lösbar (NP-vollständig), deswegen wird seit langem intensiv nach effizient lösbaren Spezialfällen gesucht. Die Struktur effizient lösbarer Instanzen läßt sich bemerkenswerterweise sehr genau durch ein „Räuber-und-Gendarmen“-Spiel auf gewissen, aus den Instanzen erzeugten Graphen beschreiben.
Ich werde in diesem Vortrag eine Übersicht über derartige strukturelle Kriterien für die effiziente Lösbarkeit von CSP geben. 


Dr. Christian Glaßer, Universität Würzburg 
Redundanz in NP-vollständigen Mengen - 7. April 2006, 13:00 Uhr, Raum 224, Appelstraße 4 
Nach der Berman-Hartmanis-Vermutung sind alle NP-vollständigen Mengen p-isomorph. Dies ist äquivalent zur Aussage: Alle NP-vollständigen Mengen sind paddable. Der Begriff "paddable" beschreibt eine sehr starke Form der Redundanz in Mengen. Bisher sind kaum Indizien für oder wider die Berman-Hartmanis-Vermutung bekannt. Deshalb ist auch die Frage nach der Redundanz NP-vollständiger Mengen ungeklärt.
In dieser Arbeit zeigen wir, dass alle NP-vollständigen Mengen eine schwächere Form der Redundanz besitzen. Genauer sind alle NP-vollständigen Mengen mitotisch. Dies bedeutet, dass sich jede NP-vollständige Menge in eine beliebige Anzahl von NP-vollständigen Mengen partitionieren lässt (wobei die Partitionierung durch Polynomialzeitmengen geleistet wird). Unser Resultat lässt sich auf Klassen wie PSPACE, EXP, NEXP und Stufen der PH verallgemeinern. Auf diese Weise beantworten wir mehrere offene Fragen von Ambos-Spies, Buhrman, Hoene und Torenvliet. 


Dr. Wolfgang Merkle, Universität Heidelberg,  
Eine abstrakte Beschreibung ressourcenbeschränkter Reduzierbarkeiten - 7. April 2006, 14:30 Uhr, Raum 224, Appelstraße 4 
In der theoretischen Informatik wird eine Vielzahl von ressourcenbeschränkten Reduzierbarkeiten betrachtet, welche sich durch die betrachteten Ressourcenschranken unterscheiden, sowie durch die Art und Weise, wie auf die Orakelmenge zugegriffen werden kann. Beispielsweise gibt es polynomiell zeitbeschränkte und logarithmisch platzbeschränkte Reduzierbarkeiten, und beim Orakelzugriff kann man nach der Anzahl der zulässigen Anfrage an das Orakel unterscheiden und danach, ob diese Anfragen adaptiv oder nicht-adaptiv gestellt werden.
Die Strukturen, welche durch die verschiedenen Reduzierbarkeiten jeweils auf der Klasse der rekursiven Sprachen induziert werden, weisen viele Gemeinsamkeiten auf, insbesondere sind diese Strukturen dichte obere Halbverbände, enthalten minimale Paare und erlauben die Einbettung beliebiger abzählbarer Ordnungen und Boole'scher Algebren. Diese Eigenschaften können im Rahmen einer abstrakten oder axiomatischen Beschreibung resourcenbeschränkter Reduzierbarkeiten abgeleitet werden, welche im Vortrag vorgestellt wird.  


Thomas Schneider, Universität Jena 
Neue Komplexitätsresultate für hybride Logiken über transitiven Rahmen - 22. November 2005, 10:30 Uhr, Raum 224, Appelstraße 4 
Dieser Vortrag berichtet über Ergebnisse aus der gemeinsamen Arbeit "Complexity of Hybrid Logics over Transitive Frames" von Martin Mundhenk, Thomas Schneider (beide Uni Jena), Thomas Schwentick und Volker Weber (beide Uni Dortmund). Wir untersuchen das Erfüllbarkeitsproblem für hybride Logik (einer Erweiterung modaler Aussagenlogik) bezüglich Modellen, in denen die Sichtbarkeitsrelation transitiv ist.
Das überraschendste Resultat ist die NEXPTIME-Vollständigkeit der aussdrucksstarken "downarrow"-Sprache, die über der Klasse aller Modelle unentscheidbar ist. Des Weiteren geben wir Resultate für das Erfüllbarkeitsproblem verschiedener hybrider und hybrider temporaler Sprachen in den Komplexitätsklassen EXPTIME, 2EXPTIME, "nichtelementar entscheidbar" und coRE an. 


Thomas Schneider, Universität Jena 
Die Komplexität hybrider Logiken über transitiven Rahmen - 26. April 2005, 13:30 Uhr, Raum 224, Appelstraße 4  
Modale Logik ist eine ausdrucksstarke Erweiterung der klassischen Aussagenlogik. Eine Ausprägung davon ist temporale Logik, mit deren Hilfe man das zeitliche Verhalten von Dingen beschreiben kann. Dort kann man zusätzlich zur Sprache der klassischen Aussagenlogik über Operatoren verfügen, die besagen, "es gibt einen Zeitpunkt in der Vergangenheit/Zukunft, zu dem phi wahr ist" (Future/Past) oder "in der Zukunft wird phi wahr sein, und bis dahin gilt immer psi"' (Until bzw. Since).
Temporale Logik wird über Rahmen interpretiert. Das sind Strukturen, die aus einer Menge von Zeitpunkten und einer binären Relation ("später als") bestehen. Ohne Zweifel ist die Klasse aller transitiven Rahmen eine der wichtigsten Klassen für temporale Anwendungen.
Will man Zeitpunkte direkt benennen, so reicht das Ausdrucksvermögen der "einfachen" temporalen Logik nicht aus. Hybride Logik besitzt zusätzlich sprachliche Mittel, die das leisten. So kann man Zeitpunkten Namen zuweisen (mittels Nominals), zu benannten Zeitpunkten springen (mittels des at-Operators) und Variablen an Zeitpunkte binden (mittels des downarrow-Operators).
Über die Komplexität des Erfüllbarkeitsproblems für hybride Sprachen ist bereits einiges bekannt: Je nach Umfang der Sprache und zugrunde liegender Klasse von Rahmen (der Strukturen, über denen die jeweilige Logik interpretiert wird) sind NP-, PSPACE-, EXPTIME- und Unentscheidbarkeitsresultate bekannt. Allerdings gibt es Lücken für bestimmte Sprachen über eingeschränkten Klassen von Rahmen, von denen wir zwei schließen konnten. Wir zeigen, dass das Erfüllbarkeitsproblem über transitiven Rahmen für die hybride Sprache mit Since und Until EXPTIME-vollständig ist. Dies ist dieselbe Komplexität wie für diese Sprache über allgemeinen Rahmen. Wir beweisen außerdem, dass das Erfüllbarkeitsproblem über transitiven Rahmen für Fragmente zweier hybrider downarrow-Sprachen unentscheidbar ist. 


Elmar Böhler, Universität Würzburg 
Über den Verband der Clones unter FP - 12. April 2005, 11:00 Uhr, Raum 224, Appelstraße 4  
Ein Clone ist eine Menge von unter allgemeiner Substitution abgeschlossener Funktionen. Unter den Komplexitätsklassen finden sich einige Clones, wie z.B. FP, FL, FNCi und FPSPACE, die Funktionsversionen von P, L, NCi und PSPACE.
Es ist allgemein bekannt, dass die Menge der Subclones eines jeden Clones einen Verband bildet. So ist etwa ein Verband von Clones unterhalb von FP zu finden, der FL und jede der FNCi Klassen enthält. Wir wissen aber fast nichts über diesen Verband, obwohl ein solches Wissen womöglich hilfreich sein könnte, um Näheres über die genaue Beziehung von z.B. P und L herauszufinden.
Der Vortrag ist über den Verband unter FP. Wir werden über seine Größe sprechen und uns vor allem mit den Klassen beschäftigen, die direkt unterhalb von FP zu finden sind. 


Prof. Edith Hemaspaandra, Rochester Institute of Technology 
The Complexity of Poor Man's Logic - 17. März 2005, 13:30 Uhr, Raum 027, Appelstraße 4 
Motivated by description logics, we investigate what happens to the complexity of modal satisfiability problems if we only allow formulas built from literals, ∧, â—Š, and ☐. Previously, the only known result was that the complexity of the satisfiability problem for K dropped from PSPACE-complete to coNP-complete (Schmidt-Schauss and Smolka, 1991 and Donini et al., 1992). We show that not all modal logics behave like K. In particular, we show that the complexity of the satisfiability problem with respect to the class of models in which each world has at least one successor drops from PSPACE-complete to P, but that in contrast the satisfiability problem with respect to the class of models in which each world has at most two successors remains PSPACE-complete. As a corollary of the latter result, this also solves the open problem from Donini et al.'s complexity classification of description logics (Donini et al., 1997). 


Prof. Johannes Köbler, Humboldt Universität Berlin 
Komplexität von Graphisomorphie auf eingeschränkten Graphklassen - 03. Dezember 2004, 13:00 Uhr, Raum 027, Appelstraße 4 
Wir bestimmen die Komplexität des Iso- und Automorphieproblems für spezielle Graphen und Hypergraphen, indem wir es als vollständig für gewisse Komplexitätsklassen innerhalb von NC2 nachweisen. Unter anderem betrachten wir das Isomorphieproblem für Bäume und für gefärbte (Hyper-)Graphen, wobei die Anzahl der mit derselben Farbe gefärbten Knoten beschränkt ist und der gesuchte Isomorphismus die Knotenfarbe erhalten muss. 


Prof. Ulrich Hertrampf, Universität Stuttgart
Kuchenschneide-Algorithmen - 12. Mai 2004, 14:00 Uhr, Raum 224, Appelstraße 4  
Das gerechte Aufteilen eines Kuchens ist in der Realität ein unlösbares Problem. (Das wissen zumindest alle Eltern mit mehr als einem Kind.)
In diesem einführenden Vortrag zum Thema Kuchenschneiden sollen daher neben den einschlägigen Definitionen und trivialen Verfahren auch einige nützliche Tipps zur Lösung des einen oder anderen Spezialfalls gegeben werden.
Es handelt sich hier nicht um einen Forschungsvortrag - die vorgestellten Inhalte entstammen dem Buch:
"Cake-Cutting Algorithms" von J. Robertson und W. Webb (A K Peters, Natick, MA, 1998)  


Thomas Schneider, Universität Jena 
Die Komplexität modaler Logiken - 16. Januar 2004, 13:30 Uhr, Raum 224, Appelstraße 4  
Modale Logik, die "Logik der Notwendigkeit und Möglichkeit", ist eine ausdrucksstarke Erweiterung der klassischen Aussagenlogik (AL). Mit ihrer Hilfe kann man über das Wissen von Personen und Personengruppen urteilen, Aussagen über die zeitliche Veränderung von Dingen treffen oder das Verhalten von Computerprogrammen untersuchen. Dadurch ist modale Logik ein wertvolles und modernes Hilfsmittel nicht nur in der Philosophie, sondern auch für die künstliche Intelligenz und andere Bereiche der theoretischen Informatik.
Ähnlich wie für AL kann man für modale Aussagenlogik ein Erfüllbarkeitsproblem betrachten und sich nach dessen Entscheidbarkeit und Komplexität fragen. Während SAT für AL bereits hinreichend bekannt ist und komplexitätstheoretisch untersucht wurde, ist seine Entsprechung in der modalen Aussagenlogik bei Weitem noch nicht erschöpfend untersucht. Ein Grund dafür ist die Tatsache, dass es sehr viele verschiedene Systeme und "Typen" modaler Aussagenlogik gibt, die sich durch ihre syntaktische und semantische Charakterisierung mehr oder weniger stark voneinander unterscheiden und dadurch verschiedene Herangehensweisen bei der Untersuchung der Komplexität des Erfüllbarkeitsproblems erfordern.
In meinem Vortrag werde ich bekannte modale Systeme syntaktisch und semantisch charakterisieren und zueinander in Beziehung setzen. Auf dieser Vorarbeit aufbauend stelle ich aus der Literatur bekannte Komplexitätsresultate sowie eigene Ergebnisse für die NP- bzw. PSPACE-Vollständigkeit bestimmter Logiken vor. 


Dr. Matthias Kriesell, Universität Hannover 
Verbindbarkeit und Trennbarkeit in allgemeinen Graphen - 19. Dezember 2003, Raum 224, Appelstraße 4  
Viele fundamentale Eigenschaften realer Netzwerke lassen sich durch Zusammenhangsbedingungen beschreiben, etwa die Anfälligkeit gegen den Ausfall einzelner Elemente, die vorhandenen Verbindungs- oder Fluss-Kapazitaeten, Verteilung und Gestalt von Engpässen, Erreichbarkeit einzelner Elemente etc.
Zusammenhang ist daher eines der wichtigsten Konzepte der Graphentheorie. In der Vergangenheit sind zwei Modelle zur Beschreibung eines hohen Zusammenhangs zwischen zwei Elementen a, b eines Graphen vorgeschlagen worden: Die vielfältige Verbindbarkeit, bei der das Vorhandensein möglichst vieler unabhängiger Wege von a nach b gefordert wird, und die erschwerte Trennbarkeit, bei der verlangt wird, dass die Unterbrechung aller Wege von a nach b nicht durch Löschung von wenigen Elementen gelingen kann.
Einer der klassischen Sätze der Graphentheorie, der Satz von Menger, zeigt, dass Verbindbarkeit und Trennbarkeit aequivalente Konzepte sind. So besagt eine Variante, dass zwischen je zwei Knoten a, b eines Graphen genau dann k Wege ohne gemeinsame Kanten bestehen, wenn sich a von b nicht durch weniger als k Kanten trennen lässt, wenn also nach Loeschung von weniger als k beliebigen Kanten immer noch ein Weg von a nach bbesteht.
Im Vortrag werde ich die klassischen Varianten des Mengerschen Satzes behandeln und darstellen, wie sich diese in ihren Details erheblich voneinander abweichenden Aussagen von der verallgemeinernden Warte einer uebergeordneten diskreten Struktur aus als Spezialisierungen betrachten lassen.


Dr. Wolfgang Merkle, Universität Heidelberg 
Das Hutproblem und zufällige Binärfolgen - 31. Oktober 2003, Raum 224, Appelstraße 4  
Beim Hutproblem mit k Spielern wird jedem der k Mitspielern durch Münzwurf ein roter oder blauer Hut zugeteilt. Die Spieler sehen jeweils nur die Hüte der anderen Spieler, nicht aber den eigenen. Jeder Spieler kann einen Tipp bezüglich der Farbe seines Hutes abgeben, das Spiel ist gewonnen, wenn mindestens einer richtig und keiner falsch geraten hat. Die Mitspieler können vor dem Spiel eine gemeinsame Strategie festlegen, während des Spiels haben sie aber keinerlei Möglichkeit sich zu verständigen und es ist ihnen auch nicht bekannt, ob und wie die anderen tippen. Obwohl jeder einzelne Tipp zwangsläufig mit Wahrscheinlichkeit 1/2 falsch ist, gibt es für alle k der Form 2l-1 eine Strategie, bei welcher das Spiel mit Wahrscheinlichkeit 1-1/(k+1) gewonnen wird.
Das Hutproblem wurde von Ebert und Vollmer ursprünglich im Zusammenhang mit Autoreduktionen zufälliger Folgen eingeführt, hat aber inzwischen auch außerhalb der theoretischen Informatik Beachtung gefunden (siehe New York Times vom 10. April 2001 und ZEIT vom 3. Mai 2001).
Eine unendliche Binärfolge A(0)A(1) .... heißt zufällig bezüglich einer gegebenen Klasse von Wettstrategien, falls beim sukzessiven Wetten auf die jeweils nächste Stelle A(n), ähnlich wie Wetten auf Rot und Schwarz beim Roulette, der Gewinn beschränkt bleibt. Folgen die bezüglich total berechenbarer Wettstrategien zufällig sind heißen rek-zufällig.
Man kann sich nun fragen, inwieweit sich Stellen zufälliger Folge aus den restlichen Stellen berechnen lassen. Formal heißt eine Folge A autoreduzierbar auf einer Menge E, falls es einen Algorithmus gibt, welcher bei Eingabe n unter Verwendung der Werte A(m) für m ungleich n entweder A(n) oder den Wert "?" ausgibt, wobei für alle n in E tatsächlich A(n) ausgegeben wird. Fordert man zusätzlich, dass der Algorithmus nicht nur für die Folge A sonder auch für alle andere Folgen bei alle Eingaben terminiert, heißt A truth-table autoreduzierbar auf E.
Es lässt sich leicht zeigen, dass rek-zufällige Folgen nicht truth-table-autoreduzierbar auf einer unendlichen berechenbaren Menge sein können. Andererseits gilt überraschenderweise, dass jede rek-zufällige Folge in polynomieller Zeit truth-table autoreduzierbar auf einer unendlichen Menge ist.
Man kann sich weiter fragen, wie dicht bei einer Autoreduktion einer zufälligen Folge A die Stellen n liegen können, an denen A(n) tatsächlich berechnet wird. Formal heißt eine Folge A autoreduzierbar mit Dichte a(n) falls A autoreduzierbar ist auf einer Menge E, welche für alle n mindestens einen Anteil von a(n) der ersten n Stellen enthält. Beispielsweise ist eine Folge autoreduzierbar mit Dichte 1/2 falls mindestens die Hälfte der Bits von A berechnet wird.
Für rek-zufällige Folgen lassen sich die erreichbaren Dichten gut charakterisieren. Rek-zufällige Folgen sind nie truth-table-autoreduzierbar mit konstanter Dichte a(n)>0, aber für jede berechenbare nichtfallende und unbeschränkte Funktion b ist jede rek-zufällige Folge truth-table-autoreduzierbar mit Dichte a(n)=1/b(n).
Dem Vortrag liegt eine gemeinsame Arbeit mit Todd Ebert und Heribert Vollmer zugrunde.  


Dr. Sven Kosub, TU München 
Dichtebasierte Clusterung - 4. Juni 2003  
Konzepte für Kantendichten in Graphen liefern Ansätze, die zentral für die Bewältigung vielfältiger Clustering-Probleme in Netzwerken sind. Beispielsweise verwenden heutige Internet-Suchmaschinen Ranking- und Suchverfahren, die auf der Identifizierung von Gruppen untereinander hochgradig verlinkter Web-Seiten beruhen. Aber auch beim Layout-Entwurf von VLSI-Schaltkreisen kommen dichtebasierte Ansätze zum Einsatz, z.B. um durch Zusammenfassung von Teilgraphen mit einer bestimmten Kantendichte eine hierarchische Graphrepräsentierung zu gewinnen, auf deren Grundlage Schaltkreise in verschiedene Komponenten zerlegt werden können.
Von besonderem Interesse aus algorithmischer Sicht ist, wie schwierig es werden kann, dichte Teilstrukturen in Graphen zu erkennen. Dazu werden in diesem Vortrag ein Reihe von Techniken und Härteresultaten vorgestellt und diskutiert. 


Dr. Steffen Reith, 3SOFT 
Kryptographie in KFZ-Steuergeräten - 5. Mai 2003  
In heutigen Kraftfahrzeugen werden eine Vielzahl von eingebetteten Systemen für verschiedenste Steuerungsaufgaben eingesetzt. Um die Flexibilität und Wartbarkeit beim Einsatz solcher Systeme zu verbessern, werden die verwendeten CPUs mit Flashspeichern ausgestattet, die eine Neuprogrammierung in der Werkstatt zulassen. Da diese Steuergeräte auch sicherheitskritische Aufgaben lösen (z.B. Motorsteuerung), werden kryptographische Methoden zur Sicherung verwendet. Der Vortrag gibt einen Einblick in diese Problematik anhand praktischer Aufgabenstellungen. 


Dr. Jochen Schoof, 3SOFT 
Echtzeit-Betriebssysteme in Kfz-Steuergeräten - 28. April 2003  


Prof. Uwe Schöning, Universität Ulm 
Stochastische Algorithmen für das Erfüllbarkeitsproblem - 6. Januar 2003  
Das Problem festzustellen, ob eine gegebene Boolesche Formel mit n Variablen erfüllbar ist, genannt SAT, ist NP-vollständig. Auch das Problem 3-KNF-SAT ist NP-vollständig, bei dem die Formel in konjunktiver Normalform mit 3 Variablen pro Klausel dem Algorithmus präsentiert wird. Der einfache deterministische Ansatz zum Lösen solcher Fragestellungen besteht darin, alle 2n in Frage kommenden Möglichkeiten systematisch durchzuprobieren. In diesem Vortrag wird gezeigt, dass stochastische Algorithmen, wie neuerdings bekannt ist, auch in diesem Kontext deterministische Algorithmen weit hinter sich lassen können. Der beste Algorithmus für das 3KNFSAT-Problem ist stochastisch und muss im Durchschnitt nur etwa 1.33n Fälle in Betracht ziehen. Im Vergleich zum deterministischen Ansatz können Formeln mehr als doppelt so vielen Variablen in derselben Rechenzeit bearbeitet werden. Der Vortrag stellt die Grundprinzipien derartiger Algorithmen vor. 


Prof. Thomas Schwentick, Universität Marburg 
Automaten, Logik und XML - 25. November 2002  
Daten im Internet werden zunehmend in XML-Dokumenten repräsentiert. XML-Dokumente sind, trotz der Möglichkeit beliebiger Querverweise, zunächst baumartig organisiert. Bei der Untersuchung von Anfragesprachen, Typisierungssprachen und Transformationssprachen für solche baumartigen Daten spielen Konzepte aus dem Bereich der Formalen Sprachen eine große Rolle.
  • Zur Auswertung von Anfragen wurden verschiedene Arten von Baumautomaten untersucht.
  • Die Navigation in XML-Dokumenten verwendet reguläre Ausdrücke.
  • Die Typbeschreibung von Dokumenten führt zu regulären Baumsprachen.
  • Auch die Transformation von XML-Dokumenten lässt sich durch Baumautomaten modellieren.
Die enge Verbindung zwischen Automaten und geeigneten Logiken, wie der monadischen Logik zweiter Stufe, ermöglicht zuweilen eine deklarative Formulierung von Anfragen und Transformationen, die dann von Automaten ausgewertet werden können. 


Prof. Martin Mundhenk, Universität Jena 
Guter Plan ist teuer - über das Planen mit Markoff'schen Entscheidungsprozessen und dessen Komplexität - 28. Oktober 2002  
Markoff'sche Entscheidungsprozesse modellieren steuerbare stochastische Systeme, bei denen der genaue Zustand des Systems nicht unbedingt bekannt ist. Anwendungen dieses Modells finden sich z.B. bei Qualitätskontrollen, medizinischen Entscheidungssystemen, Wartungssystemen usw. Ein Plan für einen solchen Prozess sagt einem, wie der Prozess abhängig von dem Wissen über seinen Zustand gesteuert werden soll. Ziel ist es, einen Plan zu finden, der eine Gewinnfunktion maximiert.
In diesem Vortrag wird eine Einführung in Markoff'sche Entscheidungsprozesse gegeben. Anschließend wird betrachtet, wie schwierig die Suche nach einem optimalen Plan oder dessen Annäherung ist und durch welche Parameter sie beeinflusst wird. 


Prof. Klaus W. Wagner, Universität Würzburg 
Wie robust ist BPP? - 5. Juli 2002  
Eine kleine Modifizierung der Definition von BPP führt zur vermutlich stärkeren Klasse SBP, von der sich überraschenderweise herausstellt, dass sie zwischen den Arthur-Merlin-Klassen AM und MA liegt. Eigenschaften der Klasse SBP und Beziehungen zu anderen Komplexitätsklassen wedern untersucht.