Laboratory of Mathematical Logic at PDMI

Пятница, 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^-.
Рассматривается связный граф~, степени вершин которого не менее трех. Доказывается, что ограничение на долю вершин степени три, входящих в подграфы , позволяет гарантировать большее количество висячих вершин в остовном дереве такого графа. Все оценки снизу на количество висячих вершин доказываются с помощью полиномиальных алгоритмов.

Понедельник, 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?
Предлагается одна переформулировка обратного метода Маслова в терминах дизъюнктов и "супердизъюнктов", а также отношение этого метода к методу резолюций.

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

Докладчик: Г. В. Давыдов, И. М. Давыдова.

ПОДСЧЕТ МЕРЫ ПРОПОЗИЦИОНАЛЬНЫХ ФОРМУЛ
Формуле F в КНФ сопоставляется мера m(F) так, что условие m(F) = 1 эквивалентно невыполнимости . Для подсчета меры предлагается последовательное ипользование принципа "включения-исключения". Классы формул, для которых предложенный метод полиномиален, характеризуются в терминах структуры графа совместности, соответствующего формуле .

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

пятница, 27 апреля 2001 г., 17:00, к.106
Состоится ДВА доклада.
17:00. Докладчик: С.Норин
НИЖНЯЯ ОЦЕНКА ДЛЯ K-ОГРАНИЧЕННЫХ НЕЗАВИСИМЫХ ОТНОСИТЕЛЬНО МИНИМУМА СЕМЕЙСТВ ПЕРЕСТАНОВОК
Семейство C перестановок чисел от 1 до n называется k-ограниченным независимым относительно минимума, если для любого X - набора чисел от 1 до n, такого, что |X|<=k, и любого x из X Pr(min{p(X)}=p(x))=(1/|X|), где |X| - число элементов множества X, p - перестановка из С.
Будет приведено доказательство полиномиальной нижней оценки для k-ограниченных независимых относительно минимума семейств перестановок, что значительно улучшает ранее известные оценки.
19:00. Докладчик: В.П.Оревков
ПРОДОЛЖЕНИЕ
доклада
МЕТОДЫ ПОИСКА ДОКАЗАТЕЛЬСТВ ДЛЯ СКУЛЕМОВСКОГО ФРАГМЕНТА ИСЧИСЛЕНИЯ ПРЕДИКАТОВ

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

Докладчик: В. П. Оревков.

МЕТОДЫ ПОИСКА ДОКАЗАТЕЛЬСТВ ДЛЯ СКУЛЕМОВСКОГО ФРАГМЕНТА ИСЧИСЛЕНИЯ ПРЕДИКАТОВ
Предваренная формула исчисления предикатов находится в скулемовской форме, если в ее префиксе кванторы существования предшествуют кванторам всеобщности. В докладе будут рассмотрены: 1) варианты сведения формул к скулемовскому виду; 2) методы элиминации функциональных знаков; 3) метод резолюций и обратный метод для скулемовского случая; 4) разрешимые подклассы исчисления предикатов.