General Information
| Instructor(s) | Pascal Amsili, Angelo Ortiz Tandazo (TA) |
| Place, time |
Tuesdays, 16:00-18:00 (CM); Fridays, 16:00-18:00 (TA sessions). ENS 29 rue d'Ulm, room Ribot Starting February 4. Note that the class will exceptionally start at 16:30 on Feb. 7th. |
| Credits | 6 ECTS |
| Prerequisites | Interest for linguistics (but talk with the instructor) |
| Course taught in | English |
| Teaching format | On-site teaching. Students who need to follow the class off-site should contact the instructor asap. See below for detailed course policies. |
| Links | Schedule ; Moodle ; Master de Sciences Cognitives (ancien CogMaster). |
| Previous classes |
This class was previously taught with a different format (3 hours per week), with a slightly different
audience (students from the CogMaster), at a different stage of the curriculum. Yet the following
pages offer resources that may be relevant (slides, previous exams, exercices with answers,
etc.): 2023/24 ; 2022/23 ; 2021/22 ; 2020/21 ; 2019/20. |
Schedule (tentative)
| wk. | date | type | description | links |
|---|---|---|---|---|
| 1 | 2024-02-04 | CM & TD | Formal Languages: first contact | slides; exercise sheet |
| 2024-02-07 | Formal Language Theory (FLT): Formal Languages | slides used in class | ||
| 2 | 2024-02-11 | CM | FLT 2: Regular Languages | slides (planned) |
| 2024-02-14 | TD | Automata, Regular expressions, Regular Grammars | ||
| 3 | 2024-02-18 | CM | FLT 3: Formal Grammars and Complexity | |
| 2024-02-21 | TD | Formal grammars | ||
| - | 2024-02-25 | CM | No class (academic break) | |
| 2024-02-28 | TD | |||
| - | 2024-03-04 | CM | No class (PSL Week) | |
| 2024-03-07 | TD | |||
| 4 | 2024-03-11 | CM | FLT 4: Complexity of natural language(s) | |
| 2024-03-14 | TD | Formal grammars | ||
| 5 | 2024-03-18 | CM | First Order Logic (FOL): Crash course in propositional logic | |
| 2024-03-21 | TD | Propositional logics, predicate logic | ||
| 6 | 2024-03-25 | CM | FOL 2: Predicate logic | |
| 2024-03-28 | TD | Predicate logic | ||
| 7 | 2024-04-01 | CM | FOL 3: Quantification in natural language | |
| 2024-04-04 | TD | Advanced predicate logic | ||
| 8 | 2024-04-08 | CM | Compositionality and Lambda-Calculus (CLC): Typed λ-calculus | |
| 2024-04-11 | TD | First fragment | ||
| 9 | 2024-04-15 | Fragment | ||
| 2024-04-18 | TD | Fragment | ||
| - | 2024-04-22 | CM | No class (academic break) | |
| 2024-04-25 | TD | |||
| 10 | 2024-04-29 | CM | CLC 2: General Quantifiers | |
| - | 2024-05-02 | TD | No class | |
| 11 | 2024-05-06 | CM | CLC 3: English as a Formal Language | |
| - | 2024-05-09 | TD | No class | |
| 12 | 2024-05-13 | CM | Untyped λ-calculus | |
| 10 | 2024-05-16 | TD | Fragment | |
| 13 | 2024-05-20 | CM | Time, Intensionality | |
| 11 | 2024-05-23 | TD | Fragment | |
| - | 2024-05-27 | CM | No class (academic break) | |
| 2024-05-30 | TD | |||
| - | 2024-06-03 | CM | No class | |
| 12 | 2024-06-06 | TD | Fragment | |
| - | 2024-06-10 | CM | No class | |
| 13 | 2024-06-13 | Final Exam | ||
Pointers (references, bibliography, online resources)
- About First Order Logic, a 28p. hand-out (in French) that may be useful.
- About regular languages and automata, a 30p. hand-out (in French) that may be useful (covers additional material and algorithms).
- Barbara Partee, Alice ter Meulen & Robert E. Wall, Mathematical Methods in Linguistics, Kluwer Academic Publishers, 1993.
- Gamut, L. T. F. (1991). Logic, Language, and Meaning, volume 1: Introduction to Logic; volume 2: Intensional Logic and Logical Grammar. University of Chicago Press.
- About the complexity of natural language, a relatively recent survey can be found here: António Branco, 2018: Computational Complexity of Natural Languages: A Reasoned Overview.
- For those interested in pure untyped lambda-calculus : The Interactive Lambda-calculus Tracer: TILC aims to be a friendly visual tool for teaching/studying main basic pure untyped lambda-calculus concepts.
- More directly relevant to the fragment construction process we've been practicing: the lambda-calculator (formerly the Penn Lambda Calculator).
- More about λ-calculus: very useful lecture notes from this class:
CS 152, Programming Languages (Harvard, 2016):
- Pure language,
- Combinators,
- Typed language (the last one is less relevant for us).
- A recent book about computability and complexity was recently published at MIT Press (author Hubie Chen), and the first part, which is published under a creative commons licence, is a very precise and complete chapter on automata theory. Available HERE.