Winter term 2017/18


Description Logics, Constraint Satisfaction Problems and MMSNP

Organisation: Usually every Friday 10 - 12 AM, APB 3027

Contact: Maximilian Pensel


Summer term 2017


Automata Theory

Every Friday, 8:00 o'clock, Technische Universität Dresden, APB 3027

Contact: Luisa Herrmann


Existential Theory of the Reals

Wednesday, 15:00 o'clock, Technische Universität Dresden WIL C115 (or C37), starting March 15 2017

Contact: Caterina Viola


Winter term 2016/17


Reasoning in Description Logics using Automata

Friday, 2:00 PM, TU Dresden, APB 3027

Contact: Pavlos Marantidis


Summer term 2016


Automata on Graphs

Every second Thursday, 14:00 o'clock, Universität Leipzig, A426

Contact: Stefan Dück


Stochastic Games

Tuesdays, 9:15 AM, Technische Universität Dresden, Communication Room at the Institut für Algebra

Contact: Antoine Mottet


Winter term 2015/16


Automata on Graphs

Every second Thursday, 14:00 o'clock, Universität Leipzig, A426

Contact: Stefan Dück


Until summer term 2015


Probabilistic Model Checking

By appointment, Technische Universität Dresden, APB 3025

Contact: Christel Baier


Weighted Tree Automata

  • Summer Term 2014
  • Fortnightly meetings to discuss papers and distribute reading material
  • Contact: Markus Teichmann markus.teichmann at mailbox.tu-dresden.de

Literature

  • Maletti & Fülop & Vogler - Weighted Extended Tree Transducers [2]
  • Kallmeyer - Multiple Context-Free Grammars and Linear Context-Free Rewriting Systems [3, Chapter 6]
  • Seki & Kato - On the Generative Power of Multiple Context-Free Grammars and Macro Grammars [4]
  • Fujiyoshi & Kasai - Spinal-Formed Context-Free Tree Grammars [1]
  • Seki & Matsumura & Fujii & Kasami - On multiple context-free grammars [5]

References

[1] A. Fujiyoshi and T Kasai. “Spinal-Formed Context-Free Tree Grammars”. English. In: Theory of Computing Systems 33.1 (2000), pp. 59–83.
[2] Z. Fülöp, A. Maletti, and H. Vogler. “Weighted extended tree transducers”. In: Fundamenta Informaticae 111 (2011), pp. 163–202.
[3] L. Kallmeyer. Parsing Beyond Context-Free Grammars. Cognitive Technologies. Springer, 2010.
[4] H. Seki and Y. Kato. “On the Generative Power of Multiple Context-Free Grammars and Macro Grammars”. In: IEICE - Trans. Inf. Syst. E91-D.2 (Feb. 2008), pp. 209–221.
[5] H. Seki, T. Matsumura, M. Fujii, and T. Kasami. “On multiple context-free grammars”. In: Theoretical Computer Science 88.2 (1991), pp. 191 –229.

The EL family of Description Logics

Monday 14:00, Technische Universität Dresden, INF 3027

Contact: Andreas Ecke

Until Summer Term 2014


Automata for data words and data trees

Wednesday 15:00, Universität Leipzig, A416

Until summer term 2014

Contact: Vitaly Perevoshchikov


Description Logics and Numbers - Concrete and Fuzzy

Thursday 14:00, Technische Universität Dresden, INF 3027

Contact: Stefan Borgwardt

Summary:

Description Logics (DLs) are a family of logic-based formalisms for knowledge representation and reasoning. We investigated extensions of DLs by means of quantitative reasoning, in particular concrete domains and probabilistic semantics. We studied the proof techniques used to derive the complexity or undecidability of reasoning problems in these logics.

For concrete domains, decidability of reasoning in several extensions of ALC was shown using tableau algorithms and automata-based approaches. Undecidability in the presence of a transitive closure operator can be shown using a reduction from the Post Correspondence Problem.

Decidability of consistency in several variants of Prob-ALC, a probabilistic extension of ALC, was shown using a type elimination approach to construct so-called quasimodels.

Literature:

  • Franz Baader, Philipp Hanschke: A Scheme for Integrating Concrete Domains into Concept Languages, 1991.
  • Umberto Straccia: Managing Uncertainty and Vagueness in Description Logics, 2008.
  • Joseph Halpern: An Analysis of First Order Logics of Probability, 1990.
  • Carsten Lutz, Lutz Schröder: Probabilistic Description Logics for Subjective Uncertainty, 2010.
  • Carsten Lutz: Combining Interval-Based Temporal Reasoning with General TBoxes, 2003.
  • Carsten Lutz, Maja Miličić: A Tableau Algorithm for DLs with Concrete Domains and GCIs, 2007.

Winter term 2012/13


Temporal Real-Time Logics

Every Wednesday 14:30, Universität Leipzig, Room P410

Contact: Karin Quaas


Weighted Tree Automata

Winter Term 2013/2014, fortnightly meetings to discuss papers and distribute reading material

Contact: Markus Teichmann markus.teichmann at mailbox.tu-dresden.de

Literature

  • Context Free Tree Grammars (CFTG)
    • Engelfriet & Schmidt - IO and OI (I & II) [3, 4]
    • Guessarian - Pushdown Tree Automata [9]
    • Engelfriet & Vogler - Pushdown Machines for the Macro Tree Transducer [5]
  • Weighted Tree Grammars
    • Alexandrakis & Bozapalidis - Weighted Grammars and Kleene’s Theorem [1]
    • Ésik & Kuich - Formal Tree Series [6]
    • Bozapalidis, Fülöp & Rahonis - Equational Weighted Tree Transformations [7]
  • Tree Transducers
    • Engelfriet - Bottom-up and Top-down Tree Transformations: A Comparison [2]
    • Maletti, Fülöp & Vogler - Weighted Extended Tree Transducers [8]
  • Application in NLP: Tree Adjoining Grammars
    • Kepser & Rogers - The Equivalence of Tree Adjoining Grammars and Monadic Context-free Tree Grammars [10]

References

[1] A. Alexandrakis and S. Bozapalidis. Weighted grammars and Kleene’s theorem. Information Processing Letters, 24(1):1–4, 1987.
[2] J. Engelfriet. Bottom-up and top-down tree transformations a comparison. Mathematical systems theory, 9(2):198–231, 1975.
[3] J. Engelfriet and E. M. Schmidt. IO and OI. I. Journal of Computer and System Sciences, 15(3):328 – 353, 1977.
[4] J. Engelfriet and E. M. Schmidt. IO and OI. II. Journal of Computer and System Sciences, 16(1):67–99, 1978.
[5] J. Engelfriet and H. Vogler. Pushdown machines for the macro tree transducer. Theoretical Computer Science, 42(0):251 – 368, 1986.
[6] Z.Ésik and W. Kuich. Formal tree series. Journal of Automata, Languages and Combinatorics, 8(2):219–285, 2003.
[7] S. Bozapalidis, Z. Fülöp, and G. Rahonis. Equational weighted tree transformations. Acta Inf., 49(1):29–52, 2012.
[8] Z. Fülöp, A. Maletti, and H. Vogler. Weighted extended tree transducers. Fundamenta Informaticae, 111:163–202, 2011.
[9] I. Guessarian. Pushdown tree automata. Mathematical systems theory, 16(1):237–263, 1983.
[10] S. Kepser and J. Rogers. The equivalence of tree adjoining grammars and monadic linear context-free tree grammars. Journal of Logic, Language and Information, 20(3):361–384, 2011.