Logik in der Informatik Prof. Dr. Nicole Schweikardt

Aktuelles

Einführung

Anhand von Originalarbeiten und ergänzender Literatur werden im Seminar aktuelle Themen der Theoretischen Informatik erarbeitet.

Ziele sind das Kennenlernen neuer Forschungsergebnisse, das Verstehen wissenschaftlicher Originaltexte, die Fähigkeit zur Einordnung der Inhalte und Beweistechniken, sowie deren Wiedergabe in eigener Darstellung in einem begrenzten Zeitrahmen.

Das Seminar richtet sich an fortgeschrittene Studierende in einem Diplom- oder Masterstudiengang, die sich im Bereich Theoretische Informatik spezialisieren wollen. Die Teilnahme am Seminar setzt Kenntnisse, die in den Vorlesungen "Ausgewählte Kapitel der Logik", "Logik und Komplexität" oder "Einführung in die Datenbanktheorie" vermittelt werden, voraus.

Ort und Zeit

Zeit und Raum

Mittwochs, 15:30-17:00 Uhr im Johann von Neumann-Haus (Rudower Chaussee 25), Raum 3.408

 

Veranstalter/in

Prof. Dr. Nicole Schweikardt

Vorträge

Nach und nach wird hier eine Liste der Vortragstermine angegeben.

Datum	Vortragende/r	Thema
25.04.18	Nicole Schweikardt Fabian Gerhardt	Vorbesprechung und Themenvergabe und erster Vortrag: Aufzählung der Ergebnistupel von azyklischen konjunktiven Anfragen mit konstanter Verzögerung
Donnerstag, 03.05.18, 13h00 (s.t.)	Benjamin Hauskeller	Dynamic Query Evaluation of Conjunctive Queries under Bag Semantics
23.05.18	Fabian Gerhardt	Vortrag zu Thema 2: Das Faktorisierungs-Wald Theorem von Simon
30.05.18	Dr. Hubie Chen (University of London)	The Logic of Counting Query Answers: A Study via Existential Positive Queries
13.06.18	Tobias Löffler	Thema 4: Lernen von MSO-definierbaren Hypothesen auf Strings
04.07.18	Dr. Sebastian Siebertz (Univ. of Warsaw)	Deciding first-order properties of nowhere dense graphs Abstract: Nowhere dense graph classes form a large variety of classes of sparse graphs, including the class of planar graphs, actually all classes with excluded minors or topological minors, and classes of bounded expansion. We proved in 2013 that deciding properties of graphs definable in first-order logic is fixed-parameter tractable on nowhere dense graph classes. In this tutorial we introduce nowhere dense graph classes with a focus on the properties of these classes that are used in the first-order model-checking algorithm. We then sketch a proof of our model-checking result.
11.07.18, 15h15 bis 17h00	Sarah Kleest-Meißner und David Luis Wiegandt	Thema 7: Das Zählen von Dreiecken in einem Graphen unter Updates (Teile 1 und 2)
18.07.18	Dr. Christoph Berkholz	Thema 1: Faktorisierte Datenbanken
Donnerstag, 19.07.18, 11h00 (s.t.)	Prof. Dr. Domenico Sacca (Univ. of Calabria)	Count Constraints: Definition, Complexity and Emerging Applications Abstract: A typical problem in database theory is to verify whether there exists a relation (or database) instance satisfying a number of given dependency constraints. This problem has received a renewed deal of interest within the context of data exchange, but the issue of handling constraints on aggregate data has not been much investigated so far, notwithstanding the relevance of aggregate operations in exchange systems. In this talk, we introduce count constraints that require the results of given count operations on a relation to be within a certain range. Count constraints are defined by a suitable extension of first order predicate calculus, based on set terms, and they are then used in a new decisional problem, the Inverse OLAP: given a star schema, does there exist a relation instance satisfying a set of given count constraints? The new problem turns out to be NEXP complete under various conditions: program complexity, data complexity and combined complexity. Count constraints can be also used into a data exchange system context, where data from the source database are transferred to the target database using aggregate operations. In this framework, we show how to enrich source data with additional background information and knowledge patterns on the application domain, derived by previous analysis of experiences from both experts and simple users. We shall therefore investigate the following challenge: devising a data exchange setting for enhancing the information content of source data. As an example, given raw data about restaurants and post reviews, we want to classify the restaurants according to the various "dimensions" (i.e., categorized properties or other features) that have been singled out and evaluated in the reviews. Domenico Sacca is full professor of Computer Engineering at the University of Calabria since 1987. From 2009 on, he is also President of the Computing and Telecommunication Competence Center ICT-SUD, operating in five regions of Southern Italy: Calabria, Campania, Puglia, Sardegna and Sicilia. From January 2002 to January 2009, he was Director of the CNR (the Italian National Research Council) Research Institute ICAR (Institute for High Performance Computing and Networking), located in Rende (CS) and branches in Naples and Palermo. He was also visiting scientist at IBM Laboratory of San Jose, at the Computer Science Department of UCLA and at the ICSI Institute of Berkeley; moreover, he was scientific consultant of MCC, Austin. His current research interests focus on advanced issues of databases such as: data and process mining, inverse data mining, data warehousing, compressed representation of datacubes, database query languages. Recently he is also conducting some research activities on cyber security topics such as protection of systems, services and end users as well as on privacy issues. His list of publications contains more than 150 papers on journals (including Journal of the ACM, SIAM Journal on Computing, ACM Transactions on Database Systems, Theoretical Computer Science, IEEE Transactions on Software Engineering, IEEE Transactions on Knowledge and Data Engineering, VLDB Journal, Information Systems, ACM Transactions on Knowledge Discovery from Data) and on proceedings of international conferences.

Mögliche Vortragsthemen

1. 2 Vorträge zum Thema Faktorisierte Datenbanken: Kompakte Repräsentation von Anfrageergebnissen durch f-Repräsentationen und d-Repräsentationen.
   Literatur:
   Dan Olteanu und Jakub Závodný. "Size Bounds for Factorised Representations of Query Results". ACM Trans. Database Syst. 40, Nr. 1 (März 2015): 2:1-2:44. LINK.
2. 2 Vorträge zum Thema Das Faktorisierungs-Wald Theorem von Simon: Kompakte Repräsentationen von regulären Sprachen und deren Anwendungen.
   Literatur:
   Mikolaj Bojanczyk: "Factorization Forests". In Proc. DLT 2009, pp. 1-17. LINK.
   und
   Mikolaj Bojanczyk: "Algorithms for regular languages that use algebra". SIGMOD Record 41(2): 5-14 (2012). LINK.
3. 2 Vorträge zum Thema Der Beweis von Courcelles Vermutung: Graphklassen beschränkter Baumweite sind genau dann in modulo-Zähl-MSO-Logik CMSO definierbar, wenn die Klasse ihrer Baumzerlegungen von einem Baumautomaten erkennbar ist.
   Während die Hin-Richtung dieser Aussage seit langem als "Courcelles Theorem" bekannt (und nicht Teil dieses Seminarvortrags) ist, löst die Rück-Richtung ein Problem, das mehr als 25 Jahre lang offen war. Zum Beweis werden u.a. eine neue und sehr nützliche Sichtweise auf MSO-Interpretationen sowie das Faktorisierungs-Wald Theorem von Simon genutzt.
   Literatur:
   Mikolaj Bojanczyk und Michal Pilipczuk: "Definability equals recognizability for graphs of bounded treewidth". In Proc. LICS 2016, pp. 407-416. LINK.
4. 1 Vortrag zum Thema Lernen von MSO-definierbaren Hypothesen auf Strings: Unter Verwendung des Faktorisierungs-Wald Theorems von Simon wird ein Lernverfahren entwickelt, das in einer Linearzeit-Vorverarbeitungsphase eine Indexstruktur aufbauen kann, mit deren Hilfe MSO-Hypothesen auf Strings in Zeit polynomiell in der Größe der Trainingsdaten gelernt werden können.
   Literatur:
   Martin Grohe, Christof Löding, Martin Ritzert: "Learning MSO-definable hypotheses on strings". In Proc. ALT 2017, pp. 434-451. LINK. Eine etwas ausführlichere Vorabversion findet sich hier: LINK.
5. 1 Vortrag zum Thema Überdeckungen von Anfrageergebnissen: Kompakte Repräsentationen von Anfrageergebnissen für Join-Anfragen.
   Literatur:
   Ahmet Kara, Dan Olteanu: "Covers of Query Results". In Proc. ICDT 2018, 16:1-16:22. LINK.
6. 1 Vortrag zum Thema Verfahren und untere Schranken zum Aufzählen aller unabhängigen Mengen eines Graphen: Diese Arbeit ist ein "Klassiker" und eine der ersten Arbeiten, die sich mit der Komplexität von Aufzählungsproblemen beschäftigte.
   Literatur:
   David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis: "On Generating All Maximal Independent Sets". Inf. Process. Lett. 27(3): 119-123 (1988)
7. 2 Vorträge zum Thema Das Zählen von Dreiecken in einem Graphen unter Updates: Diese Arbeit liefert eine neue, worst-case optimale Datenstruktur zum Zählen der in einem Graphen vorkommenden Dreiecke, die die Modifikation des Graphen durch Einfügen oder Löschen von Kanten unterstützt.
   Literatur:
   Ahmet Kara, Hung Q. Ngo, Milos Nikolic, Dan Olteanu und Haozhe Zhang: "Counting Triangles under Updates in Worst-Case Optimal Time". Vorabversion erschienen als arXiv:1804.02780v1 [cs.DB] 9. Apr 2018. 21 Seiten. LINK.

Spielregeln

1. Rechtzeitige Vereinbarung und Wahrnehmung eines Sprechstundentermins, der mindestens 1 Woche vor dem eigenen Seminarvortrag stattfindet und während dem ein detailliertes Vortragskonzept inkl. Vortragsfolien/Tafellayout vorgelegt wird,
2. einen Vortrag zu einem der oben genannten Themen zu halten (Dauer: 60 Minuten, plus 10 Minuten zur Diskussion und zur Klärung von Fragen aus dem Publikum),
3. Anwesenheit an mind. 75% aller Vorträge und
4. Abgabe einer schriftlichen Ausarbeitung des Vortragsthemas: Länge ca 5 Seiten (mindestens 4, maximal 7), Layout wie in der Layout-Vorlage angegeben, Deadline: Ende der Vorlesungszeit des Sommersemesters 2018 als pdf-Datei per Email zu senden an Prof. Dr. Nicole Schweikardt.