Winter term 2020/21
Deep Learning
Wednesday, biweekly, 14:30, Online
Contact: Filippo De Bortoli
Summer term 2020
Approximate Sequentiality of Weighted Tree Automata
Tuesday, 11:00, Online
Contact: Frederic Dörband
Summer term 2019
Graph Structure and Monadic Second Order Logic
Wednesday, 15:00, Technische Universität Dresden, APB 3027
Contact: Willi Hieke
Sequentiality of Weighted Tree Automata
Tuesday, 11:00, Universität Leipzig, A416
Contact: Frederic Dörband
Ramsey classes with closures and forbidden homomorphisms
Thursday, 14:45, Technische Universität Dresden, Willersbau C41
Contact: Simon Knäuer
Winter term 2018/19
Description Logic
Monday, 14:30, Technische Universität Dresden, APB 3027
Contact: Willi Hieke
Summer term 2018
Automata over Sets with Atoms
Wednesday, 14:00 o'clock, Universität Leipzig, A426
Contact: Karin Quaas
Automata theory in Bioinformatics/NLP
Organisation: one Tuesday per month, 10:45 AM, Universität Leipzig
Contact: Shima Asaadi
Probabilistic Model Checking
By appointment, Technische Universität Dresden, APB 3025
Contact: Christel Baier
Winter term 2017/18
The Proof of the PCP Theorem
Monday, 13:15 o'clock, Technische Universität Dresden, WIL C115, first meeting: Nov 6 2017
Contacts: Jakub Opršal, Caterina Viola, Antoine Mottet
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.
