Research Seminar Logic and Automata
Regular schedule (by arrangement):
Monday, 13:30–14:30, Room 4116 (Seminar Room Informatik 7)Subscribe to calendar
- The Discrete Strategy Improvement Algorithm for Solving Parity Games and Complexity Measures for Directed Graphs
Tuesday, 17 April 2012, 12:00, Seminar Room of Informatik 7 (Room 4116)
Felix Canavoi RWTH Aachen University
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
Thursday, 30 August 2012, 11:00, Seminar Room of Informatik 7 (Room 4116)
Nikolas Breuckmann RWTH Aachen University
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.
In this seminar topics of current research within the areas of theoretical computer science, logic, and complexity theory are presented. Presentations may be given by the members of our research groups, students, and guests. Accordingly, this seminar offers the opportunity to stay up-to-date on recent developments in the subject areas mentioned above and, for students, to find possible topics for diploma theses.
There is a mailing list for talk announcements. You can subscribe to or unsubscribe from the list via its web interface. For further questions please contact aglua(at)automata.rwth-aachen.de.
If you wish to give a talk, please contact aglua(at)automata.rwth-aachen.de.