Пятница, 7 декабря, ПОМИ РАН, ауд. 106. Начало в 14:00.
Докладчик: С.Л. Кузнецов (Математический институт им. В.А. Стеклова РАН).
Тема: Звёздочка Клини в структурах с делениями.
Abstract
Итерация, или звёздочка Клини, является одной из наиболее интересных алгебраических операций, встречающихся в теоретической информатике. В докладе будет рассказано о поведении этой операции в частично упорядоченных структурах, содержащих операции деления. Операции деления проще всего объяснить с лингвистической точки зрения, на алгебре формальных языков над некоторым алфавитом. Например, если S — язык, состоящий из всех правильно построенных предложений, а N — язык имён существительных, то к языку N\S будут относиться непереходные глаголы (если к такому глаголу приписать слева существительное, то получится правильное предложение); в N\S/N будут переходные глаголы, и т.д. Поскольку формальные языки в общем случае некоммутативны (порядок букв и слов имеет значение), различают левое и правое деления. Звёздочка Клини также естественно вписывается в эту лингвистическую модель: например, S* будет множеством правильных текстов (конечных последовательностей предложений). Другой естественный пример — алгебра бинарных отношений на некотором множестве, где звёздочка Клини — это рефлексивно-транзитивное замыкание. Если понимать бинарное отношение как некоторое (недетерминированное) действие на множестве состояний: xRy, если при действии R система переходит из состояния x в состояние y, — то деление R\S соответствует действию, которое, будучи предварено действием R, даст действие S. В таком случае звёздочка Клини R* означает повторение действия R несколько (возможно ноль) раз. В общем же случае звёздочку Клини a* можно определять по-разному: как предел n-ых степеней a (с помощью омега-правила) или посредством какой-либо из разновидностей индуктивного определения. Будет рассказано как об известных, так и о новых результатах о соотношениях между этими подходами, об алгоритмической сложности соответствующих логик (эквациональных теорий), о полноте и неполноте относительно упомянутых выше естественных интерпретаций.
Приложение
