Mathematical Logic and Discrete Mathematics at PDMI

Пятница, 15 марта, комната 106. Начало в 18:00.

Докладчик: Б. Ф. Мельников (Ульяновский гос.университет).

ПРОСТОЕ РЕШЕНИЕ ПРОБЛЕМЫ ЗВЕЗДНОЙ ВЫСОТЫ (Часть I)
Проблема звездной высоты регулярного языка была поставлена в самом начале 1960-х годов и очень долгое время оставалась нерешенной. Кратко сама проблема может быть сформулирована следующим образом: определяем звездную высоту (ЗВ) регулярного выражения (РВ) как максимальное вложение в нем операции "звезда"; известно, что для каждого регулярного языка (РЯ) существует бесконечно много РВ, определяющих этот язык; существует ли алгоритм, определяющий, какое именно из этих РВ имеет минимальную ЗВ? В 1987-м году вышла пока единственная публикация с довольно сложным алгоритмом, решающим данную проблему (K.Hashiguchi).
Автор данных тезисов предлагает значительно более простое решение, базирующееся на построении специальных недетерминированных конечных автоматов (КА). Данное решение является продолжением серии работ автора, связанных с исследованием РЯ с помощью т.н. функций разметки состояний КА; в тех работах, среди прочих, были решены задачи минимизации КА по другим критериям - вершинной и дуговой.
Вторая часть доклада состоится на заседании семинара лаборатории математической логики ПОМИ в понедельник, 18 марта в 14:00, к.203.

Пятница, 1 марта, комната 106. Начало в 18:00.

Докладчик: Э. Гирш (совместная работа с Д.Григорьевым и Д.Пасечником).

ПОЛУАЛГЕБРАИЧЕСКИЕ ДОКАЗАТЕЛЬСТВА
Вывод пропозициональной тавтологии в полуалгебраической системе доказательств заключается в опровержении некоторой системы полиномиальных неравенств. Эти системы являются довольно сильными: в них имеются короткие доказательства принципа Дирихле, Цейтинских тавтологий, нераскрашиваемости k-клики в (k-1) цвет и т.д. Тем не менее, для наиболее слабых из полуалгебраических систем получены экспоненциальные нижние оценки на длину вывода.

Пятница, 8 февраля, комната 106. Начало в 18:00.

Докладчик: В. Б. Балакирский (EIDMA, Eindhoven University of Technology).

HASHING OF DATABASES WITH THE USE OF METRIC PROPERTIES OF THE HAMMING SPACE
We describe hashing of databases as a problem of information and coding theory. It is shown that the triangle inequality for the Hamming distances between binary vectors can essentially decrease the computational efforts of searching for a pattern in databases. Introduction of the Lee distance in the space, which consists of the Hamming distances, leads to a new metric space where the triangle inequality is effectively used.

Пятница, 28 декабря, комната 106. Начало в 18:00.

Докладчик: О. Етеревский.

УНИФИКАЦИЯ И ЕЕ ПРИЛОЖЕНИЯ К ПРОБЛЕМЕ РАЗРЕШИМОСТИ
Унификация (unification) -- это подстановка в два терма вместо переменных других термов, так чтобы получившиеся термы совпали. Естественно, это возможно не для любых двух термов. В докладе приводится алгоритм, работающий за полиномиальное время, проводящий унификацию. В алгоритме используются ориентированные графы без циклов (dag). Дается оценка на сложность задачи унификации. Из этой оценки, в свою очередь, следует оценка на сложность проблемы разрешимости для Эрбрановских формул.

Пятница, 21 декабря, комната 106. Начало в 18:00.

Докладчик: Л. Мелещук.

О СУЩЕСТВОВАНИИ РАЗЛИЧНЫХ ТИПОВ РАСШИРИТЕЛЕЙ (***продолжение***)
Расширители (expanders) широко применяются в различных областях современной дискретной математики и информатики. Существует несколько различных определений расширителя. В докладе будут затронуты вопросы о связи между этими определениями, о теоремах существования расширителей и о конкретных конструкциях.

Пятница, 14 декабря, комната 106. Начало в 18:00.

Докладчик: Л. Мелещук.

О СУЩЕСТВОВАНИИ РАЗЛИЧНЫХ ТИПОВ РАСШИРИТЕЛЕЙ
Расширители (expanders) широко применяются в различных областях современной дискретной математики и информатики. Существует несколько различных определений расширителя. В докладе будут затронуты вопросы о связи между этими определениями, о теоремах существования расширителей и о конкретных конструкциях.

Пятница, 19 октября, комната 106. Начало в 18:00.

Докладчик: В. Жижкун.

МОДАЛЬНЫЕ ЛОГИКИ И СЕМАНТИКИ КРИПКЕ
Модальные логики получаются из традиционной пропозициональной добавлением новых "модальных" операторов и "модальных" аксиом (примеры: логика возможности/необходимости, темпоральная логика). Весьма удобным средством не только для интерпретации, но и для исследования получающихся формальных аксиоматических систем оказались модели Крипке (1960-е гг.), системы отношений над множествами.
В докладе будет рассказано, что из себя представляют семантики Крипке (relational structures) и как они могут быть использованы.
Изложение основано на первой главе книги P. Blackburn, M. de Rijke, Y. Venema. "Modal Logic". (http://www.mlbook.org)

Пятница, 14 сентября, комната 106. Начало в 17:00.

Докладчик: Д. В. Карпов.

СВЯЗЬ КОЛИЧЕСТВА ВИСЯЧИХ ВЕРШИН В ОСТОВНОМ ДЕРЕВЕ КУБИЧЕСКОГО ГРАФА И КОЛИЧЕСТВА ПОДГРАФОВ K_4^-.
Рассматривается связный граф~$G$, степени вершин которого не менее трех. Доказывается, что ограничение на долю вершин степени три, входящих в подграфы $K_4^-$, позволяет гарантировать большее количество висячих вершин в остовном дереве такого графа. Все оценки снизу на количество висячих вершин доказываются с помощью полиномиальных алгоритмов.

Понедельник, 3 сентября, комната 106. Начало в 14:30.

понедельник, 3 сентября 2001 г., в 14:30 в ауд. 203
Vladimir Grebinskiy, Compugen Inc.
Design and Applications of Oligo Based Micro Arrays.
Abstract
In this talk I'll describe a new tool of modern biology (oligo based micro arrays) and its use in medical dignostics, as well as computational problems in the design of optimal oligos.
No previous biological knowledge required.
Обращаю ваше внимание на нестандартное время проведения семинара

Пятница, 25 мая, комната 106. Начало в 17:00.

Докладчик: Б. Ю. Конев.

Доклад по статье В.Лифшица
WHAT IS THE INVERSE METHOD?
Предлагается одна переформулировка обратного метода Маслова в терминах дизъюнктов и "супердизъюнктов", а также отношение этого метода к методу резолюций.