Аннотация:
Итерация, или звёздочка Клини — это одна из наиболее интересных алгебраических операций, используемых в теоретической информатике. Алгебраические структуры с итерацией Клини, развившиеся из известной алгебры регулярных выражений, широко используются для описания формальных языков и для моделирования вычислительных процессов. В связи с этим интерес представляют алгебраические логики для структур с итерацией — т.е. логические исчисления, описывающие тождества, истинные в таких структурах — их алгоритмическая разрешимость и сложность. Эти логики оказываются неклассическими (точнее, субструктурными) вариантами логики высказываний, однако, за счёт индуктивной природы звёздочки Клини, приобретают некоторые черты намного более сильных систем, таких как формальная арифметика. В докладе будет дан обзор результатов об алгебраических логиках с итерацией Клини, как ранее известных, так и принадлежащих докладчику.
