Seminar Logic, Complexity, Games: Logics for Reasoning about Uncertainty, Dependence and Independence

WS 2019/20

Organisation

Die Veranstaltung wird als Blockseminar angeboten, die Vorträge werden am Ende des Semesters wahlweise auf deutsch oder englisch gehalten.

Die Vorträge finden in unserem Seminarraum (Raum 4116, E1, Ahornstr. 55) in der ersten Februarwoche statt. Die genauen Daten werden noch bekanntgegeben.

Die Ausarbeitungen sollen sechs Seiten umfassen und die Vorträge 25 Minuten lang sein.

Zeitplan

9. Dezember Erste Version der Ausarbeitungen
13. Januar Finale Version der Ausarbeitungen
20. Januar Erste Version der Folien
1. Februarwoche Vorträge

Inhalt

We survey logical formalisms that are designed to reason about knowledge or uncertain, unreliable, random or simply unknown data. Thereby we encounter different concepts such as knowledge representation, games with imperfect information and modern logics of dependence and independence.

Themen

Thema Vortragende(r) Betreuer(in) Literatur
Henkin Quantifiers Astrid Hagemeyer K. Dannert [BlaGur86]
Independence-Fiendly Logic Florian Nienhaus K. Dannert [IFBook]
Armstrong Axiomatisations Emma Ahrens R. Wilke [GalVaa13, HanKon14]
Complexity Thresholds in Inclusion Logic Jan Kraus B. Pago [HanHel19]
Contradictory Negation Lars Göttgens B. Pago [Gal14]
Translation between different Logics with Team Semantics Rafael Albert M. Hoelzel [Gal12a, Gal12b, Kapitel 4]
New Operators for Logics with Team Semantics Oxana Shaya M. Hoelzel [Roe18a, Roe18b, Kapitel 3,4]
Negation in Dependence Logic (Interpolation) Sophie Brinke M. Hoelzel [KonVaa11]
Counting in Team Semantics Nick Kleinmanns M. Naaf [GraHeg16]
Continuous Team Semantics Duc Khuat R. Wilke [HirKonPau19]
Modal Logic with Team Semantics Lorena Finkbeiner M. Naaf [KonMulSchVol15]
Inquisitive Modal Logic ‐ Ehrenfeucht-Fraïssé Oliver Gaul R. Wilke [CiaOtt18, Kapitel 1-4]
Inquisitive Modal Logic ‐ van Benthem characterisation Maksim Rotmann R. Wilke [CiaOtt18, Kapitel 1-3, 6, 8]
Sabotage Games Niels Lücking B. Pago [LodRoh03a, Ben05, AucBenGro17]
Sabotage Modal Logic Luca Oeljeklaus M. Naaf [LodRoh03b, Ben05]

Literatur

[AucBenGro17] G. Aucher, J. van Benthem, and D. Grossi. Modal logics of sabotage revisited. Journal of Logic and Computation, vol. 28(2), pp. 269–303, 2017.
[BarHelRon17] F. Barbero, L. Hella, and R. Rönnholm. Independence-Friendly Logic Without Henkin Quantification. In Logic, Language, Information, and Computation (J. Kennedy and R. J. de Queiroz, Eds.), pp. 14–30, Berlin, Heidelberg. Springer Berlin Heidelberg, 2017.
[Ben05] J. Benthem. An essay on sabotage and obstruction. In Mechanizing Mathematical Reasoning, pp. 268–276. Springer, 2005.
[BlaGur86] A. Blass and Y. Gurevich. Henkin Quantifiers and Complete Problems. Annals of Pure and Applied Logic 32 (1986), 1-16, vol. 32, pp. 1-16, 1986.
[CiaOtt18] I. Ciardelli and M. Otto. Inquisitive bisimulation. arXiv e-prints, pp. arXiv:1803.03483, 2018.
[DHKMV18] A. Durand, M. Hannula, J. Kontinen, A. Meier, and J. Virtema. Probabilistic Team Semantics. In Foundations of Information and Knowledge Systems (F. Ferrarotti and S. Woltran, Eds.), pp. 186–206, Cham. Springer International Publishing, 2018.
[EbbLohYan13] J. Ebbing, P. Lohmann, and F. Yang. Model Checking for Modal Intuitionistic Dependence Logic. In Logic, Language, and Computation (G. Bezhanishvili, S. Löbner, V. Marra, and F. Richter, Eds.), pp. 231–256, Berlin, Heidelberg. Springer Berlin Heidelberg, 2013.
[FagHalMosVar95] R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning about Knowledge. MIT Press, 1995.
[Gal12a] P. Galliani. Inclusion and Exclusion Dependencies in Team Semantics: On Some Logics of Imperfect Information. Annals of Pure and Applied Logic, vol. 163(1), pp. 68–84, 2012.
[Gal12b] P. Galliani. The Dynamics of Imperfect Information. PhD thesis, University of Amsterdam, 2012.
[Gal14] P. Galliani. On Strongly First-Order Dependencies. arXiv e-prints, pp. arXiv:1403.3698, 2014.
[GalHel13] P. Galliani and L. Hella. Inclusion Logic and Fixed Point Logic. Leibniz International Proceedings in Informatics, LIPIcs, vol. 23, pp. , 2013.
[GalVaa13] P. Galliani and J. Väänänen. On Dependence Logic. arXiv e-prints, pp. arXiv:1305.5948, 2013.
[Gra16] E. Grädel. Games for Inclusion Logic and Fixed-Point Logic. In Dependence Logic: Theory and Applications (S. Abramsky et al., Eds.), pp. 73–98. Birkhäuser, 2016.
[GraHeg16] E. Grädel and S. Hegselmann. Counting in Team Semantics. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016) (J. Talbot and L. Regnier, Eds.), vol. 62 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 35:1–35:18, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2016.
[Hal03] J. Y. Halpern. Reasoning About Uncertainty. MIT Press, Cambridge, MA, USA, 2003.
[HanHel19] M. Hannula and L. Hella. Complexity Thresholds in Inclusion Logic. In Logic, Language, Information, and Computation (R. Iemhoff, M. Moortgat, and R. de Queiroz, Eds.), pp. 301–322, Berlin, Heidelberg. Springer Berlin Heidelberg, 2019.
[HanKon14] M. Hannula and J. Kontinen. A Finite Axiomatization of Conditional Independence and Inclusion Dependencies. In Foundations of Information and Knowledge Systems (C. Beierle and C. Meghini, Eds.), pp. 211–229, Cham. Springer International Publishing, 2014.
[HirKonPau19] A. Hirvonen, J. Kontinen, and A. Pauly. Continuous Team Semantics. In Theory and Applications of Models of Computation (T. Gopal and J. Watada, Eds.), pp. 262–278, Cham. Springer International Publishing, 2019.
[IFBook] A. L. Mann, G. Sandu, and M. Sevenster. Independence-Friendly Logic - a Game-Theoretic Approach. Cambridge University Press, 2011.
[KonMulSchVol15] J. Kontinen, J. Müller, H. Schnoor, and H. Vollmer. A Van Benthem Theorem for Modal Team Semantics. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015) (S. Kreutzer, Ed.), vol. 41 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 277–291, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015.
[KonVaa11] J. Kontinen and J. Väänänen. A Remark on Negation in Dependence Logic. Notre Dame J. Formal Logic, vol. 52(1), pp. 55–65, 2011.
[LodRoh03a] C. Löding and P. Rohde. Solving the sabotage game is PSPACE-hard. In International Symposium on Mathematical Foundations of Computer Science, pp. 531–540, 2003.
[LodRoh03b] C. Löding and P. Rohde. Model checking and satisfiability for sabotage modal logic. In International Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 302–313, 2003.
[Roe18a] R. Rönnholm. Capturing k-ary existential second-order logic with k-ary inclusion-exclusion logic. Ann. Pure Appl. Logic, vol. 169(3), pp. 177–215, 2018.
[Roe18b] R. Rönnholm. Arity Fragments of Logics with Team Semantics. PhD thesis, University of Tampere, 2018.

Zuordnung

  • Mathematik (B.Sc.)/Seminare
  • Informatik (B.Sc.)/Seminare
  • Informatik (M.Sc.)/Seminar Theoretische Informatik
  • Mathematik (M.Sc.)/Seminar: Logik, Komplexität, Spiele (Reine Mathematik)

Voraussetzungen

  • Modul Mathematische Logik
  • für B.Sc. Informatik: bestandenes Modul "Einführung in das wissenschaftliche Arbeiten (Proseminar)"

Rückfragen

Erich Grädel, Richard Wilke, Matthias Hoelzel, Katrin Dannert, Benedikt Pago, Matthias Naaf