TKS-Seminar

Seminar im SoSe 2014

Gehalten von Prof. Dr. Nicole Schweikardt

Einführung

Das TKS-Seminar richtet sich an Mitglieder der Arbeitsgruppe Theorie komplexer Systeme sowie an alle, die Interesse an theoretischer Informatik haben.
Kreditpunkte oder ein Seminarschein können hier nicht erworben werden — dafür aber vertiefte Kenntnisse in theoretischer Informatik, insbesondere in den Bereichen Logik, Komplexitätstheorie und Datenbanktheorie.

Termine

Mi, 30.4.2014, 17:15	André Frochaux Über Bäume, mDatalog und das QCP Der Vortrag gibt einen kurzen Überblick und eine Einführung in Hinblick auf den Vortrag vom 13. Mai. Themen: verwendete (relationale) Strukturen, Syntax und Semantik von (monadischem) Datalag, Entscheidbarkeit QCP.
Di, 13.5.2014, 12:00 s.t.	André Frochaux Monadic Datalog Containment on Trees Conference Version (AMW 2014) We show that the query containment problem for monadic datalog on finite unranked labeled trees can be solved in 2-fold exponential time when (a) considering unordered trees using the axes child and descendant, and when (b) considering ordered trees using the axes firstchild, nextsibling, child, and descendant. When omitting the descendant-axis, we obtain that in both cases the problem is Exptime-complete.
Mo, 26.5.2014, 15:15	Namit Chaturvedi (RWTH Aachen) Toward a Structure Theory of Regular Infinitary Trace Languages The family of regular languages of infinite words is structured into a hierarchy where each level is characterized by a class of deterministic ω-automata - the class of deterministic Buechi automata being the most prominent among them. In this paper, we analyze the situation of regular languages of infinite Mazurkiewicz traces that model non-terminating, concurrent behaviors of distributed systems. Here, a corresponding classification is still missing. We introduce the model of "synchronization-aware asynchronous automata", which allows us to initiate a classification of regular infinitary trace languages in a form that is in nice correspondence to the case of ω-regular word languages.
Mi, 11.6.2014, 16:30	Maxime Savaro Determining elements of the obstruction set for the graphs of linear rankwidth at most 2
Mi, 9.7.2014, 16:30	Mario Holldack Ausdrucksstärke und algorithmische Eigenschaften von Abschnittsanfragen
Di, 5.8.2014, 16:00	Vladimir Gusev Synchronizing automata An automaton is called synchronizing if there is a word w and a state q such that w applied to an arbitrary state p brings it to q. This notion naturally appears in different areas of computer science. In my talk I will tell about applications of synchronizing automata and about famous open problem stated by Černý.
Di, 12.8.2014, 14:15	Berit Grußien Modular Decompositions in Descriptive Complexity Theory and a new Logic for Logarithmic Space Descriptive complexity theory is concerned with the characterization of complexity classes by means of mathematical logic. A lot of attention was given to the complexity class polynomial time (PTIME). Recently, it was shown by Grohe that fixed point logic with counting characterizes, or captures, PTIME on all classes of graphs with excluded minors. The question for further interesting graph classes for which we can find a logic capturing PTIME leads us to classes of graphs closed under induced subgraphs. In my thesis I show that fixed-point logic with counting captures PTIME on chordal comparability graphs and permutation graphs. The results are based on a graph decomposition, known as the modular decomposition, which was introduced by Gallai in 1976. These are two of few capturing results for PTIME on graph classes that are closed under induced subgraphs. Further, I turn my attention to the complexity class logarithmic space (LOGSPACE), and introduce a new logic for LOGSPACE (joint work with Grohe, Hernich and Laubner). This logic uses a new operator that allows it to formalize a limited form of recursion. It captures LOGSPACE on directed trees and interval graphs. Moreover, I show that it captures LOGSPACE on chordal claw-free graphs, which confirms and improves a conjecture of Grohe.
Do, 21.8.2014, 15:00	Frederik Harwath Expressivity and Succinctness of Order-Invariant Logics on Depth-Bounded Structures