Advanced Formal Language Theory, Spring 2022
ETH Zürich: Course catalog
Course Description
This course serves as an introduction to weighted formal language theory. The lectures cover the theory and algorithms used to manipulate and compute with weighted automata and grammars in detail. The emphasis is on rigor and depth rather than broad coverage. To motivate the theory, the course will also cover various applications of formal language theory to modern-day machine learning. Students should expect a healthy dose of proof-writing and, thus, mathematical maturity is expected. In terms of background, the class will draw on techniques from discrete math, analysis, and linear algebra. While there are no hard prerequisites, having taken a class that covers basic graph algorithms will be helpful as well as familiarity with basic real analysis and linear algebra.
Grading
The course is structured around a companion software library, called rayuela. Most of the homework exercises, which comprise 50% of the course grade, will involve implementing bits of the theory discussed in class while providing additional analysis or devising algorithms not discussed in class with the tools introduced during the lecture. The homework will be released every week in bunches of 3–4 questions but will be submitted jointly on two occasions.
The remaining 50% of the course grade will be determined by a final project of the student’s selection. The teaching staff has compiled a list of recent papers, listed below, whose replication would make for a great project, but students should feel free to come up with other ideas as well. To give early feedback, a proposal is due midway through the course.
In short, the grade for the course will be determined by the following formula:
* 50% Homeworks
* 50% Course Project
* No exam!
Organization
Lectures: Thu 12-14 (ML F 39). The lectures will be given in person. This recurring Zoom meeting will be used throughout the semester for people who want to tune in remotely. The password can be found on Moodle. Recordings can be found on the password-protected Polybox. The password is the same as the one for the Zoom meeting.
Discussion Sections: Thu 14-15 (ML F 38). Discussion sections this semester will mostly be in the form of answering questions you might have about the homeworks and the course content. They will either be in person or via Zoom (same link as lecture), depending on the preference of the teaching team.
Course Live Chat: To provide an easier way to communicate with the teaching team and your colleagues, we have set up a chat server here. It is hosted on ETH servers and it will be the main communication hub for the course! We encourage you to sign up and participate in the discussions there.
Literature:
Rayuela
Course notes will be updated throughout the semester.
A selection of related work is provided for individual lectures.
News
13.02 Class website is online!
15.02 A selection of possible project papers has been published.
08.03 The Course Project Guidelines have been published.
Syllabus
Course Project
You can find more information on the course project and the detailed instructions for it here.
Course Project Ideas
The teaching staff has compiled a list of recent papers, whose replication would make for a great project. However, you should feel free to come up with other ideas as well.
Here is the list we have compiled:
Contact
You can ask questions on Moodle or on the course chat server. Please post questions there, so others can see them and join the discussion. If you have questions which are not of general interest, please don’t hesitate to contact us directly, i.e., email Ryan with the TAs cc-ed.
