|
Course by S. L. Kuznetsov and T. G. Pshenitsyn "Algorithmic problems for formal grammars"
(September 18–December 25, 2025, Steklov Mathematical Institute, Room 104 (8 Gubkina))
We kindly ask all participants, including remote ones and those
watching recorded videos, to register at this link.
The formal grammar theory lies at the intersection of mathematical logic, theoretical computer science, and linguistics. Formal grammars are used to describe both natural languages and computer languages (for example, programming languages).
The course explores two families of grammatical formalisms viz. Chomsky generative grammars and Lambek categorial grammars. Special attention is given to grammars for which efficient (polynomial-time) parsing algorithms exist, the latter making nontrivial use of the dynamic programming approach. Such grammars are of greatest interest for applications.
Syllabus:
- Context-free grammars. Chomsky normal form. The Cocke–Younger–Kasami algorithm.
- Reduction of the parsing problem for context-free grammars to matrix multiplication (Valiant's algorithm).
- Greibach normal form.
- The Lambek calculus, Lambek categorial grammars. Equivalence of Lambek grammars and context-free grammars (Pentus' theorem).
- Proof nets for the Lambek calculus.
- Polynomial translation of Lambek grammars with one division into context-free grammars.
- NP-completeness of the derivability problem for the Lambek calculus.
- Polynomial algorithm for Lambek grammars with bounded depth.
- Tree-adjoining grammars (TAG).
- Noncontracting grammars and their generation of PSPACE-complete languages. Polynomial-time parsing algorithm for a fixed growing grammar.
- Generative grammars (type-0 grammars in Chomsky hierarchy). Algorithmic undecidability of the parsing problem for Lambek grammars with additional axioms (including the single-division fragment).
- Undecidability of the totality problem (generation of all words over a given alphabet) for context-free grammars. Languages defined by Lambek grammars with Kleene iteration.
 Lecturers
Kuznetsov Stepan Lvovich
Pshenitsyn Tikhon Grigor'evich
Financial support
The course is supported by the Ministry of Science and Higher Education of the Russian Federation (the grant to the Steklov International Mathematical Center, agreement no. 075-15-2025-303).
Institutions
Steklov Mathematical Institute of Russian Academy of Sciences, Moscow
Steklov International Mathematical Center |
|
| Course by S. L. Kuznetsov and T. G. Pshenitsyn "Algorithmic problems for formal grammars", September 18–December 25, 2025 |
|
|
December 4, 2025 (Thu) |
 |
| 1. |
Lecture 12. Algorithmic problems for formal grammars
S. L. Kuznetsov, T. G. Pshenitsyn
December 4, 2025 18:00, Steklov Mathematical Institute, Room 104 (8 Gubkina)
|
|
|
|
|
|
|
November 27, 2025 (Thu) |
|
| 2. |
Lecture 11. Algorithmic problems for formal grammars
S. L. Kuznetsov, T. G. Pshenitsyn
November 27, 2025 18:00, Steklov Mathematical Institute, Room 104 (8 Gubkina)
|
|
|
|
|
|
|
November 20, 2025 (Thu) |
|
| 3. |
Lecture 10. Algorithmic problems for formal grammars
S. L. Kuznetsov, T. G. Pshenitsyn
November 20, 2025 18:00, Steklov Mathematical Institute, Room 104 (8 Gubkina)
|
|
|
|
|
|
November 13, 2025 (Thu) |
|
| 4. |
Lecture 9. Algorithmic problems for formal grammars
S. L. Kuznetsov, T. G. Pshenitsyn
November 13, 2025 18:00, Steklov Mathematical Institute, Room 104 (8 Gubkina)
|
|
|
|
|
|
|
November 6, 2025 (Thu) |
|
| 5. |
Lecture 8. Algorithmic problems for formal grammars
S. L. Kuznetsov, T. G. Pshenitsyn
November 6, 2025 18:00, Steklov Mathematical Institute, Room 104 (8 Gubkina)
|
|
|
|
|
|
|
October 30, 2025 (Thu) |
|
| 6. |
Lecture 7. Algorithmic problems for formal grammars
S. L. Kuznetsov, T. G. Pshenitsyn
October 30, 2025 18:00, Steklov Mathematical Institute, Room 104 (8 Gubkina)
|
|
|
|
|
|
|
October 23, 2025 (Thu) |
|
| 7. |
Lecture 6. Algorithmic problems for formal grammars
S. L. Kuznetsov, T. G. Pshenitsyn
October 23, 2025 18:00, Steklov Mathematical Institute, Room 104 (8 Gubkina)
|
|
|
|
|
|
|
October 16, 2025 (Thu) |
|
| 8. |
Lecture 5. Algorithmic problems for formal grammars
S. L. Kuznetsov, T. G. Pshenitsyn
October 16, 2025 18:00, Steklov Mathematical Institute, Room 104 (8 Gubkina)
|
|
|
|
|
|
|
October 9, 2025 (Thu) |
|
| 9. |
Lecture 4. Algorithmic problems for formal grammars
S. L. Kuznetsov, T. G. Pshenitsyn
October 9, 2025 18:00, Steklov Mathematical Institute, Room 104 (8 Gubkina)
|
|
|
|
|
|
|
October 2, 2025 (Thu) |
|
| 10. |
Lecture 3. Algorithmic problems for formal grammars
S. L. Kuznetsov, T. G. Pshenitsyn
October 2, 2025 18:00, Steklov Mathematical Institute, Room 104 (8 Gubkina)
|
|
|
|
|
|
|
September 25, 2025 (Thu) |
|
| 11. |
Lecture 2. Algorithmic problems for formal grammars
S. L. Kuznetsov, T. G. Pshenitsyn
September 25, 2025 18:00, Steklov Mathematical Institute, Room 104 (8 Gubkina)
|
|
|
|
|
|
|
September 18, 2025 (Thu) |
|
| 12. |
Lecture 1. Algorithmic problems for formal grammars
S. L. Kuznetsov, T. G. Pshenitsyn
September 18, 2025 18:00, Steklov Mathematical Institute, Room 104 (8 Gubkina)
|
|
|
|
|
|
|
Contact us: