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

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