General Information

Instructor(s) Pascal Amsili
Place, time Wednesdays, 9:30-12:30 am. Starting Sept. 20. ENS 29 rue d'Ulm, salle de séminaire du DEC
Code LING 102
Credits 4 ECTS
Major Linguistics
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 Moodle link  /  Cogmaster, Linguistic Major, syllabus, schedule
Previous classes 2022-2023 ; 2021-2022 ; 2020-2021 ; 2019-2020 ;

Contrôles (assessment)

Modalités There will be four homework assignments (worth 60% of the final grade) and a final exam (worth 40% of the final grade).
Homeworks can be handed in in class (paper) or on moodle (pdf format). On moodle the deadline is 23:59.
Homework #1 (10-04) automata (due October, 25); answers
Homework #2 (10-25) grammars (due November 22); answers
Homework #3 (11-22) pred. logic (due December 20); some answers for the first question; complete answers
Homework #4 (12-20) grammar engineering (due January, 10 17); answers (in French)
Results marks (instructions)
Exam: answer Here is a partial correction of the exam given on January, 17 (questions 1 to 5).

Schedule (tentative)

2023-09-20 Seminar room Formal Language Theory (FLT): 1. Formal Languages slides.
Also relevant: slides from an ESSLLI course.
2023-09-27 Seminar room FLT: 2. Regular Languages slides
2023-10-04 Seminar room FLT: 3. Formal Grammars slides ; same slides with scribbles
2023-10-11 Seminar room FLT: 3. Formal Grammars (exercices)
FLT: 4. Complexity of NL
same slides with a couple more scribbles
2023-10-18 Seminar room FLT: Complexity of NL (end)
First Order Logic (FOL): 1. Propositional Logic

hand-out (prop) ; copy of the board
exercises (prop. logic) ; answers
2023-10-25 Marbo, 29 FOL: 2. Predicate Logic hand-out (pred);
exercises (pred. logic) answers (partial)
2023-11-01 No class (public holiday)
2023-11-08 Actes, 45 FOL: 2. Predicate Logic (end) hand-out (equivalences)
2023-11-15 Berthier, 29 Compositionality and λ-calculus (CLC): first contact
2023-11-22 Berthier, 29 CLC: Generalized Quantifiers hand-out (fragment);
2023-11-29 No class (PSL Week)
2023-12-06 No class (Job prospects day)
2023-12-13 Seminar room CLC: Untyped language ; Fragment (cont'd) slides (pure language)
2023-12-20 Berthier, 29 CLC: Fragment (cont'd) ; Time (and negation) hand-out (fragment); slides ; second hand-out
2023-12-27 No class (winter break)
2024-01-03 No class (winter break)
2024-01-10 Curie C Q&A session on the whole content;
Compositional treatment of quantification; Intensionality
slides (quantification); slides (intentionality)
2024-01-17 Berthier, 29 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):
  • 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.

Course policies

Some course policies are general to all Cogmaster courses. These common policies are:
  • Attendance is mandatory and verified. More than 2 justified absences means that students can no longer validate a course for credit (ECTS).
  • Final grades below 6/20 are eliminatory (i.e. the credits cannot count towards the 30 ECTS necessary to validate a semester).
  • There is no second session (“rattrapage”).
  • The minimal penalty for plagiarism is the removal of the ECTS from the student’s course contract.
  • Courses are indivisible; students cannot follow and validate only part of a course for partial credit.
Regular attendance of, and punctual arrival at, both lectures and TD are crucial to succeed in this course, and they are mandatory for all students registered for credit. This is important both for your individual success in this course, and for every other students’ success. Keep in mind in particular that, by arriving late, you are jeopardizing your own but also your classmates’ education by disrupting the flow of lectures. Practically speaking, if you are registered for credit then your grade will suffer from poor attendance or recurrent late arrivals. If you are not registered for credit, the same policy applies, though with different consequences: poor attendance or recurrent late arrivals may force us to ask you to stop auditing the course.
You are strongly encouraged to participate in lectures and in TD. This means asking deep and challenging questions, but also asking simple questions, asking for clarification, saying “I’m just not getting this, please explain it in some new way” or “I’m lost, can you remind me why we’re talking about this?” You can ask questions in French at any time. Contacting the instructor (and TA) by email is the best way to contact us when you have brief questions.
All homework assignments are to be handed on time either in class of on Moodle. You can write up your answers in French or in English (NB you will not lose points for grammatical mistakes!). If you hand in all of the assignments, your lowest score will be factored out. Importantly if you do not hand in all of the assignments, your lowest score (namely 0) will not be dropped, and your grade will suffer accordingly. Naturally, exceptions will be considered on a case by case basis given adequately documented extraordinary circumstances.
Discussing assignments with classmates
You are allowed (and to some extent encouraged) to discuss homework assignments with your classmates. However, two things are required if you engage in substantive discussions of solutions: (i) you must indicate in your write-up the names of classmates with which you discussed solutions in some depth, and (ii) you must write up your answers to the assignment by yourself. Under no circumstances are you to share typed-up answers to the assignments or to discuss the actual write-ups. Use this opportunity for collaboration with your classmates wisely: working with a classmate who is more comfortable than you on a particular topic can help you understand that topic better; working with a classmate who knows less than you about a particular topic can help you consolidate what you know and force you to reassess fundamental elements of your knowledge. But you should collaborate with classmates in very small groups that are relatively well balanced in terms of understanding of the material.
Academic honesty policy
Cheating will not be tolerated and may cost you your grade as well as have deeper repercussions in your academic career. The following is a non-exhaustive list of examples of what counts as cheating in this course: (i) signing on the attendance sheet without attending the class (e.g. signing and leaving, or signing for someone else); (ii) copying the homework write-up or the exam answers of another student, with or without that student’s knowledge; (iii) copying elements of your solutions of exercises from sources in the literature without giving them due credit; (iv) using the same homework to validate two courses.