Reading Group of DFG Graduiertenkolleg QuantLA
| When: | Thursdays, 1pm |
| Where: | A 416, Augustusplatz 10 |
| Contact: | drichter at informatik.uni-leipzig.de |
| Topic | Summary | Book | Chapter |
| 01. Ramsey‘s theorem | Generalisation of the pigeonhole principle | IFLT | 1.7 |
| 02. McNaughton's theorem | Büchi automata and deterministic Muller automata are equally expressive | AT | 1 |
| 03. Büchi-Landweber theorem | Result about the connection between ω-regular languages and infinite games | AT | 2 |
| 04. Semilinear sets and Parik‘s theorem | Every context-free language is letter-equivalent to a regular language, i.e. is semi-linear | IFLT | 6.9 |
| 05. Semi-Dyck set and context-free languages | Every context-free language is a homeomorphic image of the intersection of the semi-Dyck set and a regular language | IFLT | 10.4 |
| 06. Distance automata | An application of the Büchi-Landweber theorem to a decision problem for distance automata | AT | 4 |
| 07. Rabin‘s theorem | MSO on infinite trees has the same expressive power as tree automata | AT | 5 |
| 08. Courcelle‘s theorem | Every MSO formula on graphs can be evaluated in linear time on graphs that have bounded treewidth | AT | 6 |
| 09. Fixed point theory | Introduction to parts of fixed point theory that have applications in (weighted) automata theory | HWA | 2 |
| 10. Mildly context-sensitive languages | Survey of different formalisms for language classes between context-free and context-sensitive | PBCFG | 6 |
| 11. Immerman-Szelepcsényi theorem | Context-sensitive language are closed under complementation | CCL | 11 |
| 12. Tree-walking automata | Tree-walking automata cannot be determinised | AT | 7 |
| 13. Weighted automata over a field | Weighted automata over the rationals can be minimised and tested for equivalence in polynomial time | AT | 8 |
| 12. Tree-walking automata 2 | Survey of tree-walking automata | [1] | |
| 13. Visibly pushdown languages | Survey of a class of languages that lies between regular and deterministic context-free languages | [2] | |
| 14. Vector addition systems | The coverability problem for vector addition systems is decidable | AT | 9 |
| 15. First-order theory of the reals | Deciding the first-order theory of the reals using BSS machines and quantifier elimination | AT | 10 |
| 16. Presburger arithmetic | Quantifier elimination, connection to finite automata and semi-linear sets, complexity of some fragments, extensions | [3] | |
| 17. Polynomial grammars | Polynomial grammars and their application to equivalence of register automata | AT | 11 |
| IFLT | - Introduction to Formal Language Theory | - Harrison |
| AT | - An Automata Toolbox | - Bojańczyk, Czerwiński |
| HWA | - Handbook of Weighted Autoamta | - Droste, Kuich, Vogler (Ésik) |
| PBCFG | - Parsing Beyond Context-Free Grammars | - Kallmeyer |
| CCL | - Computability, Complexity, and Languages | - Davis, Sigal, Weyuker |
| [1] | - Tree-walking automata | - Bojańczyk |
| [2] | - Visibly Pushdown Languages | - Alur, Madhusudan |
| [3] | - A Survival Guide to Presburger Arithmetic | - Haase |
Usually, the last row of the table corresponds to the recent topic of the reading group. Feel free to contact me via email, if you require any further information.