Home   Papers   Teaching   CV   Leisure

Научная работа студентов

М. Р. Пентус
профессор кафедры математической логики и теории алгоритмов

Учебники

Теория формальных языков

Сложность вычислений

Исчисление Ламбека и линейная логика

Математическая лингвистика

Алгоритмы на графах

Комбинаторные алгоритмы

Комбинаторная теория слов

Сжатие текстов

Статьи для студентов 1—3-го курсов мехмата

Теория формальных языков

Сложность вычислений

Исчисление Ламбека и линейная логика

Комбинаторная теория слов

Сжатие текстов

Библиографические списки

Темы для курсовых работ

Лингвистических тем здесь нет. Кто интересуется лингвистикой и математикой, может почитать, чем занимается математическая лингвистика.

Исчисление Ламбека и линейная логика

Теория формальных языков

Логика первого порядка


R-полнота L*(/) над множеством целых чисел

Определение. Типы исчисления L*(/) строятся из переменных p1p2p3,... с помощью скобок и двуместной операции /. Множество всех таких типов обозначается Tp(/). Буквы A, B, C будут обозначать типы, а буквы Г, П, Ф  конечные последовательности типов (возможно, пустые). Секвенции исчисления L*(/) имеют вид Г → A. Единственная аксиома  A → A.
Первое правило: если выводится Ф, A → B, то выводится Ф → (B / A).
Второе правило: если выводится Ф → A и выводится Г, B, П → C, то выводится Г, (B / A), Ф, П → C.

Пример. Секвенция (p1 / (p2 / p2)) → p1 выводится в L*(/) так:
p2 → p2
→ (p2 / p2)
p1 → p1
(p1 / (p2 / p2)) → p1.

Пример. Секвенцию (p1 / (p2 / (p3 / p4))) → ((p1 / (p4 / p3)) / p2) невозможно вывести в L*(/).

Определение. Реляционной моделью называется пара (W, w), где W  произвольное рефлексивное, транзитивное бинарное отношение (рассматриваемое как подмножество декартова квадрата некоторого множества D), а w  произвольная функция из Tp(/) в множество всех подмножеств множества W, такая что (r, s) принадлежит w(B / A) тогда и только тогда, когда для каждого t, если (s, t) принадлежит w(A), то (r, t) принадлежит w(B). Секвенция A → B истинна в реляционной модели (W, w), если w(A) является подмножеством w(B).

Вопрос. Существует ли невыводимая в исчислении L*(/) секвенция A → B, истинная в каждой реляционной модели, где W — стандартный линейный порядок на множестве целых чисел?


Задача выводимости в небольших грамматиках

Вопрос. Разрешима ли задача проверки выводимости слова в порождающих грамматиках, содержащих не более 9 правил?


Распознавание общезначимости эквивалентностных формул

Пример. Формула ∀x (∀y R(x,y) ↔ ∃y R(y,x)) ↔ ∀x (∃y R(x,y) ↔ ∀y R(y,x)) общезначима (то есть истинна при любой интерпретации предикатного символа R).

Пример. Формула ∃x (∀y R(x,y) ↔ ∃y R(y,x)) ↔ ∃x (∃y R(x,y) ↔ ∀y R(y,x)) не является общезначимой.

Вопрос. Разрешима ли задача проверки общезначимости формул первого порядка, построенных из атомарных формул с использованием лишь кванторов и булевой связки ?

Курсовые и дипломные работы прошлых лет

Диссертации

Home   Papers   Teaching   CV   Leisure
 
MPАдрес: http://lpcs.math.msu.su/~pentus/problems.htm
Изменения внесены 21.04.2013.
Мати Рейнович Пентус
Телефон/факс: + 7 - 495 - 939 30 31