Seminar Theoretical Computer Science: "Automata and Logic"
Prof. Franz Baader , PD Anni-Yasmin Turhan
Course Description
Automata are widely used in logic. The seminar is about the application of automata models (e.g. finite automata, Büchi-automata, alternating automata, …) in specific logics. In this seminar each participant selects a paper from the pool of papers and prepares a report and a talk based on the paper.
Organisation
There is an initial meeting on April 20th 2018 at 9:20 (2.DS) in room APB/3027. There, topics are sketched and assigned to interested students. Further organisational matters are covered as well.
Students who cannot attend the initial meeting, but want to participate in the seminar, should contact Anni-Yasmin Turhan. The idea is that all participants present results from the paper they chose in a talk at the end of the semester.
The students taking the seminar should get acquainted with their respective topic, write a report (c. 12 pages) about it, and give a presentation (of 30 minutes) at the end of the semester. They receive indiviual supervision by a tutor.
The students are expected to stick to the following schedule.
- second week of May: mandatory meeting with the tutor
- middle of June: first complete version of the report due
- middle of July: first complete version of the presentation slides due
- late July: give the presentation and participate in the discussion
Prerequisites: Undergraduate course on automata and formal languages. Basic notions from logic would also be helpful.
SWS/Modules
SWS: –/2/–This course can be used in the following modules:
- Master-Studiengang (Medien-)Informatik: INF-AQUA (Allgemeine Qualifikationen)
- Diplom-Studiengang Informatik: INF-D-940 (Berufsspezifische Schlüsselkompetenzen)
- Master in Computational Logic: MCL-PCS (Presentation and Communication Skills)
Literature
The papers covered in the seminar are:- F. Baader, J. Hladik, and R. Peñaloza: SI! Automata Can Show PSPACE Results for Description Logics. In C. Martin-Vide, editor, Proceedings of the First International Conference on Language and Automata Theory and Applications (LATA'07), 2007.
- F. Baader, J. Hladik, C. Lutz, and F. Wolter: From Tableaux to Automata for Description Logics. In Moshe Vardi and Andrei Voronkov, editors, Proceedings of the 10th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR 2003), volume 2850 of Lecture Notes in Computer Science, pages 1–32.
- J. Hladik and U. Sattler: A Translation of Looping Alternating Automata to Description Logics. In Proc. of the 19th Conference on Automated Deduction (CADE-19), volume 2741 of Lecture Notes in Artificial Intelligence. Springer Verlag, 2003.
- Rafael Peñaloza: Automata-based Reasoning in Fuzzy Description Logics. In Tommaso Flaminio, Lluis Godo, Siegfried Gottlob, and Erich Peter Klement, editors, Proceedings of the 35th Linz Seminar on Fuzzy Set Theory, pages 106–106, 2014.
- Franz Baader and Rafael Peñaloza: Automata-based Axiom Pinpointing. Journal of Automated Reasoning, 45(2):91–129, 2010. Special Issue: Selected Papers from IJCAR 2008
- Karsten Lehmann and Rafael Peñaloza: The Complexity of Computing the Behaviour of Lattice Automata on Infinite Trees. Theoretical Computer Science, 534:53–68, 2014.