Zajednički seminar
Novosadski seminar MISANU
CMS seminar
date/vreme: 08/10/2025, 11:00
venue/mesto: Ogranak SANU, "Platoneum", Nikole Pašića 6, Novi Sad
Speaker / Predavač
Prof. Stepan Kuznetsov, Steklov Mathematical Institute of RAS; HSE University, Moscow, Russia
https://homepage.mi-ras.ru/~sk/ (home page)
Title / Naslov:
Expressive Power and Complexity for Lambek-style Categorial Grammars
Abstract / Sažetak:
Lambek grammars constitute a formal grammar framework which uses substructural logical reasoning for checking grammatical correctness of sentences. As shown by Pentus (1992), the class of languages generated by Lambek grammars coincides with the class of context-free languages. The Lambek calculus itself is decidable, being NP-complete (Pentus 2006). Linguistic applications, however, suggest various extensions and variations of the Lambek calculus. In this talk, we give a survey of results on their algorithmic complexity and on the classes of languages they generate.
About the speaker. Stepan L. Kuznetsov was born in 1988 in Russia (Soviet Union) and received his education in Moscow. In 2012, he defended his C. Sc. (≈ Ph. D.) thesis on Lambek categorial grammars, under the supervision of Prof. Mati Pentus at Lomonosov Moscow State University. Since 2013, S. L. Kuznetsov has been working as a scientific researcher at Steklov Mathematical Institute of the Russian Academy of Sciences in Moscow. In 2024, he obtained his Dr. Sc. (habilitation) degree from Steklov Institute, for research on algorithmic problems for substructural logics with Kleene star. The research of S. L. Kuznetsov is connected to linear logic formalisms, mostly non-commutative, extended with powerful modalities. The most remarkable result is undecidability of action logic, which solved a problem posed by D. Kozen in 1994.