Arbeitsgemeinschaft Logik und Automaten

Allgemeine Informationen

Veranstalter:

Lehrstuhl für Informatik 7
Lehr- und Forschungsgebiet Mathematische Grundlagen der Informatik

Regelmäßige Termine (nach besonderer Ankündigung):

Montags, 13:30–14:30, Raum 4116 (Seminarraum Informatik 7)
Kalender abonnieren

Vortragsankündigung

Symmetric Circuits and Fixed-Point Logics

Freitag, 08. November 2013, 10:30 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Anuj Dawar
University of Cambridge

Zusammenfassung:

We study queries on graphs (and other relational structures) defined by families of Boolean circuits that are invariant under permutations of the vertices. In particular, we study circuits that are symmetric, that is, circuits whose invariance is explicitly witnessed by automorphisms of the circuit induced by the permutation of their inputs. We show a close connection between queries defined on structures by uniform families of symmetric circuits and definability in fixed-point logics.

The Discrete Strategy Improvement Algorithm for Solving Parity Games and Complexity Measures for Directed Graphs

Dienstag, 17. April 2012, 12:00 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Felix Canavoi
RWTH Aachen University

Zusammenfassung:

The question whether parity games are solvable in polynomial time is a major open problem in theoretical computer science. For a long time, the discrete strategy improvement algorithm due to Jurdzinski and Vöge was regarded as a good candidate for being an efficient algorithm for solving parity games. However, Oliver Friedmann was able to construct, for all important variants of the algorithm, families of parity games with exponential lower bounds. We analyse these lower bound games with respect to several complexity measures for graphs. Our results show that the graph complexity of the lower bound games is bounded with respect to most of these measures. This strengthens Friedmann's results, showing that not only there are instances on which the strategy improvement algorithm performs badly, but moreover these instances belong to classes where efficient algorithms are known.

Logical and algorithmical aspects of rank notions over rings

Donnerstag, 30. August 2012, 11:00 Uhr, Seminarraum Informatik 7 (Raum 4116)

  Nikolas Breuckmann
RWTH Aachen University

Zusammenfassung:

The extension of logics by rank operators from linear algebra was motivated by the search for a logic which is capable of capturing PTIME. However, if the entries of a matrix are elements of a ring there are several, non-equivalent definitions of matrix rank. We analyze if there is a canonical candidate for the notion of matrix rank by analyzing their domain, relationship, computational complexity and their ability to provide a criterion for the solvability of linear equation systems over rings. We show for example that, in general, all studied rank notions fail to express the solvability of linear equation systems. Furthermore, over an important class of finite commutative rings (principal ideal rings) many rank notions fall together and become computable in polynomial time.

Inhalt

In dieser Arbeitsgemeinschaft werden Vorträge zu aktuellen Forschungsergebnissen in den Bereichen Theoretische Informatik, Logik und Komplexitätstheorie gehalten. Vortragende sind dabei MitarbeiterInnen, DiplomandInnen und Gäste. Entsprechend richtet sich die AG an MitarbeiterInnen und interessierte Studierende und bietet ein Forum sich über aktuelle Entwicklungen zu informieren, sowie mögliche Themen für eine Diplomarbeit zu finden.

Organisatorisches

Wir führen eine Mailingliste für Vortragsankündigungen in der Arbeitsgemeinschaft; über die Webseite können Sie sich in die Liste eintragen bzw. aus der Liste austragen. Für weitere Fragen schreiben Sie bitte an aglua(at)automata.rwth-aachen.de.

Zur Belegung eines Vortragstermins schreiben Sie bitte ebenfalls an aglua(at)automata.rwth-aachen.de.

Frühere Vorträge

WS 2010/11, SS 2011, WS 2010/11, SS 2010, WS 2009/10, SS 2009, WS 2008/09, SS 2008, WS 2007/08, SS 2007, WS 2006/07, SS 2006, WS 2005/06, SS 2005, WS 2004/05, SS 2004, WS 2003/04, SS 2003, WS 2002/03