Fwd: Logic Seminar: Пятница 07.12. С.Л. Кузнецов (Математический институт им. В.А. Стеклова РАН): "Звёздочка Клини в структурах с делениями"
Dmitry M. Itsykson
From: PDMI seminars <pdmi.l...@gmail.com>
Date: чт, 29 нояб. 2018 г. в 12:23
Subject: Logic Seminar: Пятница 07.12. С.Л. Кузнецов (Математический институт им. В.А. Стеклова РАН): "Звёздочка Клини в структурах с делениями"
To: <sem...@logic.pdmi.ras.ru>
Тема: Звёздочка Клини в структурах с делениями
Место: ПОМИ РАН, ауд. 106
Время: 07.12.2018, 14:00
Докладчик: С.Л. Кузнецов (Математический институт им. В.А. Стеклова РАН)
Abstract:
Итерация, или звёздочка Клини, является одной из наиболее интересных алгебраических операций, встречающихся в теоретической информатике. В докладе будет рассказано о поведении этой операции в частично упорядоченных структурах, содержащих операции деления. Операции деления проще всего объяснить с лингвистической точки зрения, на алгебре формальных языков над некоторым алфавитом. Например, если S — язык, состоящий из всех правильно построенных предложений, а N — язык имён существительных, то к языку N\S будут относиться непереходные глаголы (если к такому глаголу приписать слева существительное, то получится правильное предложение); в N\S/N будут переходные глаголы, и т.д. Поскольку формальные языки в общем случае некоммутативны (порядок букв и слов имеет значение), различают левое и правое деления. Звёздочка Клини также естественно вписывается в эту лингвистическую модель: например, S* будет множеством правильных текстов (конечных последовательностей предложений). Другой естественный пример — алгебра бинарных отношений на некотором множестве, где звёздочка Клини — это рефлексивно-транзитивное замыкание. Если понимать бинарное отношение как некоторое (недетерминированное) действие на множестве состояний: xRy, если при действии R система переходит из состояния x в состояние y, — то деление R\S соответствует действию, которое, будучи предварено действием R, даст действие S. В таком случае звёздочка Клини R* означает повторение действия R несколько (возможно ноль) раз. В общем же случае звёздочку Клини a* можно определять по-разному: как предел n-ых степеней a (с помощью омега-правила) или посредством какой-либо из разновидностей индуктивного определения. Будет рассказано как об известных, так и о новых результатах о соотношениях между этими подходами, об алгоритмической сложности соответствующих логик (эквациональных теорий), о полноте и неполноте относительно упомянутых выше естественных интерпретаций.
Seminar of the Laboratory of Mathematical Logic mailing list
https://logic.pdmi.ras.ru/cgi-bin/mailman/listinfo/seminar
Home page: http://logic.pdmi.ras.ru/~seminar/