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

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

• Учебники
• Статьи для студентов 1--3-го курсов мехмата
• Библиографические списки
• Темы для курсовых работ
• Курсовые и дипломные работы прошлых лет

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

• Хопкрофт Дж. Э., Мотвани Р., Ульман Дж. Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. М.: Вильямс, 2002. 528 с.
• Gurari E. An Introduction to the Theory of Computation. Computer Science Press, 1989.
• Tao Jiang, Ming Li, Bala Ravikumar, Kenneth W. Regan. Formal Grammars and Languages. 1998. 40 pp.
• Parks D. 2005-04-05. Lecture Notes for CS 2490 (Introduction to Theoretical Computer Science).
• Power J. 2002-11-29. Formal Language Theory and Parsing.
• Taylor R. G. 2005-04-12. Models of Computation and Formal Languages. Oxford University Press, 1998.

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

• Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
• Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо, 1999. 192 с.
• Крупский В. Н. Введение в сложность вычислений. М.: Факториал Пресс, 2006. 128 с.

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

• Lambek J. The mathematics of sentence structure // American Mathematical Monthly. 1958. Vol. 65, N 3. P. 154-170.
  Русский перевод: Ламбек И. Математическое исследование структуры предложения // Математическая лингвистика: Сборник переводов / Под ред. Ю. А. Шрейдера и др. М.: Мир, 1964. С. 47-68.
• Di Cosmo R., Miller D. Linear Logic // Stanford Encyclopedia of Philosophy. <http://plato.stanford.edu/entries/logic-linear/> (04.12.2006).

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

• Гладкий А. В., Мельчук И. А. Элементы математической лингвистики. М.: Наука, 1969. 192 с.
• Carpenter B. Type-Logical Semantics. The MIT Press, 1997. 575 pp.
• Dowty D. 2005-04-05. Ling 795D: Categorial Grammar.
• Partee B., Meulen A. ter, and Wall R. E. Mathematical Methods in Linguistics. Kluwer, 1993.

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

• Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999. 960 с.
• Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001. 288 с.
• Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.

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

• Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. СПб.: Невский Диалект; БХВ-Петербург, 2003. 654 с.
• Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 1995. 264 с.
• Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 478 с.

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

• Саломаа А. Жемчужины теории формальных языков. М.: Мир, 1986. 159 с.

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

• Романовский И. В. Дискретный анализ. СПб.: Невский диалект, 2000. 240 с.

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

• Henning Fernau. Observations on Grammar and Language Families. 1993. 27 pp.

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

• Neil Immerman. Nondeterministic space is closed under complementation. 1988. 7 pp.
• L. A. Hemaspaandra, P. Mukherji, T. Tantau. Computation with Absolutely No Space Overhead. 2002. 14 pp.
• Leen Torenvliet, Marten Trautwein. A Note on the Complexity of Restricted Attribute-Value Grammars. 1995. 18 pp.

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

• Makoto Kanazawa. Lambek calculus: Recognizing power and complexity. 1999. 14 pp.
• Erik Aarts, Kees Trautwein. Non-associative Lambek categorial grammar in polynomial time. 1995. 11 pp.
• Hans-Joerg Tiede. Proof theory and formal grammars -- applications of normalization. 2002. 21 pp.
• Wojciech Buszkowski. Finite restricted powerset models for the Lambek calculus and its extensions. 20 pp.
• Wojciech Buszkowski. Cut elimination for the Lambek calculus of adjoints. 9 pp.

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

• Christian Choffrut, Juhani Karhuma"ki. Combinatorics of words. 110 pp.

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

• Abhi Shelat. Evaluating Grammar-Based Data Compression Algorithms. 2001. 38 pp.

• Неполная библигорафия по исчислению Ламбека и близким темам (для публикаций на русском языке) в формате LaTeX
• Bibliography on Linear Logic by Iliano Cervesato et al.
• Greg Restall's Working Bibliography в формате BibTeX

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

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

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

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

• R-полнота L*(/)

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

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

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

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

R-полнота L*(/)

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

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

Пример. Секвенцию (p₁ / (p₂ / (p₃ / p₄))) → ((p₁ / (p₄ / p₃)) / p₂) невозможно вывести в 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, истинная в каждой реляционной модели?

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

Пример. Формула "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)) не является общезначимой.

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

• Дмитрий Михайлович Кирноценский
  • Сравнение фрагмента UML и ComponentSpecs. 1998.
  • О задаче поиска изоморфных подграфов. 1999.
  • Среда для грамматических архиваторов. 2000.
• Ольга Михайловна Урюпина
  • Некоторые однозначные грамматики Ламбека. 1998.
  • Алгоритмы разбиения на морфемы. 1999.
  • Об автоматическом разбиении на морфемы. 2000.
• Вера Александровна Минина
  • Необходимое условие эквивалентности формул некоммутативной линейной логики. 1999.
  • R-полнота исчисления Ламбека с операцией инволюции. 2000.
  • Полнота синтаксического исчисления Ламбека с операцией инволюции. 2001.
• Дмитрий Евгеньевич Корочкин
  • Достаточное условие живости некоторого подкласса сетей Петри. 1999.
  • Неполнота исчисления Ламбека относительно конечных классов конечных реляционных моделей. 2000.
  • Исчисление Ламбека и языки деревьев. 2001.
• Екатерина Викторовна Илюшкина
  • Необходимое условие контекстно-свободности формальных языков. 1999.
  • Пример неоднозначной контекстно-свободной грамматики. 2000.
  • О соотношении между размерностью и степенью неоднозначности КС-языков. 2001.
• Ирина Александровна Болгова
  • Построение полиномиального автомата для быстрого поиска подстрок особого вида. 2001.
  • Критерий эквивалентности типов в исчислении Ламбека с одним делением. 2002.
  • Эквивалентность типов в исчислении Ламбека с одним делением. 2003.
• Пётр Александрович Стрелков
  • Анализ современных методов поиска заданного образца в текстовых файлах. 2002.
  • Некоторые методы поиска закономерностей в программах на языке C. 2003.
  • Использование деревьев суффиксов для декодирования программ на языке C. 2004.
• Юрий Вячеславович Саватеев
  • Варианты исчисления Ламбека с одним делением. 2004.
  • Совместность типов в исчислении Ламбека с одним делением. 2005.
  • Проблема выводимости для исчисления Ламбека с одним делением. 2006.
• Алексей Наифович Сафиуллин
  • Исследование сложности выводимости конкретных контекстно-свободных языков. 2004.
  • Начальные факты, касающиеся класса порождаемых детерминированными грамматиками Ламбека языков. 2005.
  • Выводимость допустимых правил в исчислении Ламбека. 2006.
• Кирилл Валериевич Чепурин
  • О языковых моделях фрагментов коммутативного исчисления Ламбека. 2005.
  • Приложения теории информационных потоков. 2006.
  • Реляционная семантика неассоциативного исчисления Ламбека и теории информационных сетей. 2007.
• Анна Александровна Черниловская
  • Об интерполяционном свойстве и устранимости сечения в исчислении Ламбека с опреатором сферы действия. 2005.
  • О логике В. Н. Гришина и её применении в лингвистике. 2006.
  • Неконсервативность линейной логики с одним отрицанием, расширяющей LG. 2007.
• Владимир Андреевич Климонтович
  • Оптимизирующая топологическая сортировка ориентированных ациклических графов. 2006.
• Андрей Иванович Фёдоров
  • Алгоритмы сжатия, использующие грамматики. 2006.
  • Метод построения грамматики типа 1 для дополнения языка типа 1. 2007.
  • Модели исчисления Ламбека. 2008.
• Степан Львович Кузнецов
  • Об исчислении Ламбека с одним делением и двумя примитивными типами. 2007.
  • Об исчислении Ламбека с одним делением и одним примитивным типом. 2008.
  • О грамматиках, основанных на двух вариантах исчисления Ламбека. 2009.
• Александр Валентинович Харитонов
  • Полнота исчисления Ламбека относительно моделей на конечных полугруппах с делением. 2007.
  • О сложности построения минимального суффиксного автомата для скользящего окна. 2008.
  • О построении сжатого суффиксного автомата в скользящем окне. 2009.
• Алексей Андреевич Сорокин
  • Непосредственное доказательство эквивалентности различных критериев выводимости в циклической линейной логике. 2009.

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