+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Donnerstag, 24. Januar 2019, 14:00 Uhr Ort: Raum 9222, Gebäude E3, Ahornstr. 55 Referentin: Svenja Schalthöfer, M. Sc. LuF Math. Grundlagen der Informatik (Lehrgebiet Informatik 7) Thema: Choiceless Computation and Logic Abstract: Choiceless computation emerged as an approach to the fundamental open question in descriptive complexity theory: Is there a logic capturing polynomial time? The main characteristic distinguishing logic from classical computation is isomorphism-invariance. Consequently, choiceless computation was developed as a notion of isomorphism-invariant computation that operates directly on mathematical structures, independently of their encoding. In particular, these computation models are choiceless in the sense that they cannot make arbitrary choices from a set of indistinguishable elements. Choiceless computation was originally introduced by Blass, Gurevich and Shelah in the form of Choiceless Polynomial Time (CPT), a model of computation using hereditarily finite sets of polynomial size as data structures. We study the structure and expressive power of Choiceless Polynomial Time, the most promising candidate for a logic capturing polynomial time. Further, we expand the landscape of choiceless computation by a notion of Choiceless Logarithmic Space, which is, to our knowledge, the only candidate for a logic capturing logarithmic space. Es laden ein: Die Dozenten der Informatik -- Silke Cormann Sekretariat Fakultät für Mathematik, Informatik und Naturwissenschaften Informatik 7 - Logik und Theorie diskreter Systeme RWTH Aachen University Ahornstr. 55 52074 Aachen Tel. +49 241 80-21701 Fax +49 241 80-22215 cormann@informatik.rwth-aachen.de