Arbeitsgemeinschaft Logik und Automaten

Vorträge im Sommersemester 2009

A Tight Lower Bound for Determinization of Transition Labeled Büchi Automata

Montag, 27. April 2009, 13:30 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Konrad Zdanowski
LIAFA, Université Paris Diderot - Paris 7

Zusammenfassung:

(Joint work with Thomas Colcombet.)

We establish a lower bound $\Omega((1.64n)^n)$ for the problem of translating a Büchi word automaton of size ~$n$ into a deterministic Rabin word automaton when both the Büchi and the Rabin conditions label transitions rather than states. This lower bound exactly matches the known upper bound to this problem, namely $o((1.65n)^n)$.

Our result entails a lower bound when the input Büchi automaton has (as it is usual) its Büchi acceptance condition labeling states. Those lower bounds remain when the output deterministic Rabin automaton has its Rabin acceptance condition labeling states. Hence, in the standard setting, our result establishes a lower bound of $\Omega((1.64n)^n)$, while the best known lower bound was $\Omega((0.76n)^n)$. A known upper bound for the standard case is $o((2.66n)^n)$.

Fixpunktlogiken und PTIME

Donnerstag, 9. Juli 2009, 10:00 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Lukas Berthold
RWTH Aachen

Zusammenfassung:

Das zentrale offene Problem der Deskriptiven Komplexitätstheorie ist die Frage, ob es eine Logik gibt, in der genau die polynomiell berechenbaren Eigenschaften endlicher Strukturen definierbar sind. Viele solcher Eigenschaften (etwa der Zusammenhang von Graphen) sind bereits in einfachen Fixpunkterweiterungen von FO definierbar und durch weiteres Hinzufügen von Zähloperatoren erhält man mit FP+C eine robuste, ausdrucksstarke Logik. Seit längerem ist bekannt, dass FP+C echt in PTIME erhalten ist, doch erst kürzlich wurde die Nichtdefinierbarkeit in FP+C auch für ein natürliches PTIME-Problem nachgewiesen, nämlich den Rang von Matrizen über endlichen Körpern.

Im ersten Teil des Vortrages sollen natürliche Erweiterungen von FP+C um Rangoperatoren definiert und einige Resultate dazu vorgestellt werden. Im zweiten werden sogenannte Ringstrukturen eingeführt, die sich aus einfachen "ringförmigen" Teilen zusammensetzen. Die Ergebnisse hier betreffen die Interpretierbarkeit solcher Strukturen in Graphen (in FP+C) und Kanonisation auf einer Klasse von Ringstrukturen (nicht definierbar in FP+C, aber in einer Erweiterung um Rangoperatoren).

A Gandy Theorem for Abstract Structures and Applications to First-Order Definability (joint work with Oleg Kudinov)

Montag, 13. Juli 2009, 13:30 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Victor Selivanov
Novosibirsk Pedagogical University

Zusammenfassung:

We establish a Gandy theorem for a class of abstract structures and deduce some corollaries, in particular the maximal definability property for arithmetical structures in the class (i.e., any aruthmetical predicate is first-order definable). We also show that the arithmetical structures under consideration are biinterpretable (without parameters) with the standard model of arithmetic. As examples we show that the quotient structure of the $h$-quasiorder of finite $k$-labeled forests (for any $k\geq 3$) and the the structure of words (over any alphabet with at lest 2 symbols) with the infix order are in our class, so the mentioned definability results hold for these structures.

Dynamic Restriction of Choices

Dienstag, 14. Juli 2009, 13:30 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Soumya Paul
Institute of Mathematical Sciences, Chennai, India

Zusammenfassung:

We study games in which the choices available to players are not fixed, and may change during the course of play. Specifically, we consider a model in which players may switch strategies, and a global (social) decision may remove some choices, based on the strategies being adopted by players. We propose a logical formalism in which such choices are specified, and a model of bounded memory strategies in which the eventual implications of such choices can be computed, and present preliminary results.

This is joint work with R. Ramanujam and Sunil Simon of the IMSc, Chennai.

Finite-Delay Strategies in Infinite Games

Mittwoch, 22. Juli 2009, 11:45 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Wenyun Quan
RWTH Aachen University

Zusammenfassung:

Based on the work of Even and Meyer, Hosch and Landweber proved that the existence of the solution of Church's Problem by a strategy with finite delay is decidable. In our work we study Church's Problem in the framework of infinite games with MSO-conditions. We construct d-delay attractor strategies in reachability games over the corresponding d-delay game graphs, to determine the existence of winning strategies with a fixed delay for player O. We illustrate that the function representing the size of the winning region of player O in a certain game depending on the delay d is monotone, but not necessarily strictly monotone. The problem of deciding whether player O has a winning strategy with finite delay is raised. We prove that player O wins a reachability game with finite delay if and only if player O has a winning strategy with delay 2^n over the corresponding game graph with n vertices. As a consequence, we obtain a new proof for the result of Hosch and Landweber.

Dynamische Komplexität, eine Einführung und aktuelle Ergebnisse

Donnerstag, 23. Juli 2009, 10:00 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Sebastian Siebertz
RWTH Aachen University

Zusammenfassung:

Die klassische Komplexitätstheorie untersucht die Ressourcen, die benötigt werden um für ein statisches Objekt zu entscheiden ob es gewisse Eigenschaften erfüllt. In vielen Anwendungen durchläuft ein Objekt aber während des Arbeitsprozesses kleine Änderungen und nach jeder Änderung soll zur Verfügung stehen, ob das Objekt die gewünschten Eigenschaften erfüllt. Für einem solchen dynamischen Prozess kann eine Hilfsstruktur aufgebaut werden mit deren Hilfe dies wesentlich effizienter entschieden werden kann als nach jeder Änderung die Berechnung vollständig neu durchzuführen. Die dynamische Komplexitätstheorie untersucht welche Ressourcen benötigt werden um eine geeignete Hilfsstruktur aufzubauen und dann eine Anfrage zu stellen. Dieser Vortrag soll eine Einführung in die dynamische Komplexitätstheorie geben und aktuelle Ergebnisse sowie offene Fragen aus dem Bereich vorstellen.

Equivalence Problem for Unambiguous Büchi Automata

Donnerstag, 23. Juli 2009, 11:00 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Nicolas Bousquet
ENS Cachan

Zusammenfassung:

We know that the equivalence problem is, in the general case, a difficult problem, PSCAPE-complete for finite automata for example. Nevertheless the problem is polynomial for unambiguous finite automata and unambiguous finite tree automata. An automaton is unambiguous if it has at most one accepting run for each word (or tree). The proof is based on a counting argument: the number of accepting runs is the number of accepted words. We want to generalize this property for Büchi automata. Even the counting argument used for finite automata seems to be useless, we will show that the equivalence problem remains polynomial for a subclass of unambiguous Büchi automata: those which have at most one final path for each word.

Komplementierung von Büchi Automaten

Mittwoch, 23. September 2009, 10:00 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Jörg Olschewski
RWTH Aachen University

Zusammenfassung:

Die Komplementierung von nichtdeterministischen Büchi-Automaten ist eine Aufgabe, an der seit über 40 Jahren gearbeitet wird. Die effektive Konstruktion eines Komplementautomaten wurde schon von Büchi selbst angegeben. Seitdem versucht man die Größe dieser Automaten zu minimieren. In den letzten Jahren gab es einige neue Resultate, welche die bekannten oberen und unteren Schranken weiter einander angenähert haben.

In diesem Vortrag stellen wir das Komplementierungsverfahren mittels Ranking Functions vor und erklären im Besonderen ein aktuelles Resultat von Sven Schewe. Seine Konstruktion liefert eine scharfe obere Schranke für die Anzahl der Zustände des Komplementautomaten.