Математический семинар ФКН «Алгебраические логики с итерацией Клини»
Кузнецов Степан Львович
Международная лаборатория интеллектуальных систем и структурного анализа: Старший научный сотрудник
31 марта в 18:10
Докладчик: Степан Кузнецов, ФКН НИУ ВШЭ; МИАН им. В.А. Стеклова.
Тема: Алгебраические логики с итерацией Клини
Аннотация: Итерация, или звёздочка Клини — это одна из наиболее интересных алгебраических операций, используемых в теоретической информатике. Алгебраические структуры с итерацией Клини, развившиеся из известной алгебры регулярных выражений, широко используются для описания формальных языков и для моделирования вычислительных процессов. В связи с этим интерес представляют алгебраические логики для структур с итерацией — т.е. логические исчисления, описывающие тождества, истинные в таких структурах — их алгоритмическая разрешимость и сложность. Эти логики оказываются неклассическими (точнее, субструктурными) вариантами логики высказываний, однако, за счёт индуктивной природы звёздочки Клини, приобретают некоторые черты намного более сильных систем, таких как формальная арифметика. В докладе будет дан обзор результатов об алгебраических логиках с итерацией Клини, как ранее известных, так и принадлежащих докладчику.
Место проведения: Покровский бульвар, 11 аудитория R405.