Научная работа студентов
Home | Papers | Teaching | CV | Leisure |
Научная работа студентов
М. Р. Пентус
профессор кафедры математической логики и теории алгоритмов
- Учебники
- Статьи для студентов 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 с.
Статьи для студентов 1—3-го курсов мехмата |
Теория формальных языков
- 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*(/) над множеством целых чисел
Теория формальных языков
Логика первого порядка
R-полнота L*(/) над множеством целых чисел
Определение. Типы исчисления L*(/) строятся из переменных p1, p2, p3,… с помощью скобок и двуместной операции /. Множество всех таких типов обозначается 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)) не является общезначимой.
Вопрос. Разрешима ли задача проверки общезначимости формул первого порядка, построенных из атомарных формул с использованием лишь кванторов и булевой связки ↔?
Курсовые и дипломные работы прошлых лет |
- Дмитрий Михайлович Кирноценский
- Сравнение фрагмента 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.
- О длине совмещающего типа в исчислении Ламбека. 2010.
- О сетях доказательства для различных вариантов исчисления Ламбека. 2011.
- Михаил Михайлович Звонкин
- О взаимосвязи критериев выводимости секвенций в исчислении Ламбека без умножения. 2010.
- Языковые модели исчисления Ламбека с единицей. 2011.
- Языковые модели фрагментов исчисления Ламбека с операциями объединения и пересечения. 2012.
- Станислав Сергеевич Макеев
- Критерии выводимости в исчислении Ламбека. 2010.
- Эквивалентность критериев выводимости в исчислении Ламбека с одним делением. 2011.
- Сложность проблемы распознавания выводимости в исчислении Ламбека без умножения при ограничении на количество вхождений одной из связок. 2012.
- Иван Михайлович Смуров
- Поиск минимального интерполянта в исчислении Ламбека для данного множества примитивных типов. 2010.
- Минимальные постинтерполянты в исчислении Ламбека без умножения. 2011.
- Предынтерполянты и постинтерполянты в исчислении Ламбека без умножения. 2012.
- Надежда Сергеевна Рыжкова
- Некоторые правила исчисления Ламбека с положительной итерацией. 2011.
- Об исчислении Ламбека с двумя делениями и итерацией. 2012.
- Свойства категориального исчисления зависимостей. 2013.
- Натали Аларкон Лопэс
- О решении некоторых уравнений в исчислении Ламбека с одним делением. 2012.
- Поиск вывода в исчислении Ламбека с одним делением. 2013.
- Различные аксиоматизации фрагментов исчисления Ламбека. 2014.
- Анастасия Сергеевна Александрова
- Сравнение сетей доказательства для некоммутативной линейной логики. 2014.
Диссертации |
- Юрий Вячеславович Саватеев. Алгоритмическая сложность фрагментов исчисления Ламбека : дис. … канд. физ.-мат. наук. 2009.
- Степан Львович Кузнецов. Категориальные грамматики, основанные на вариантах исчисления Ламбека : дис. … канд. физ.-мат. наук. 2012.
- Алексей Андреевич Сорокин. Об отношении совместимости в исчислении Ламбека и в его варианте с операциями замещения : дис. … канд. физ.-мат. наук. 2014.
Home | Papers | Teaching | CV | Leisure |
Адрес: http://lpcs.math.msu.su/~pentus/problems.htm Изменения внесены 01.10.2019. Мати Рейнович Пентус Телефон/факс: + 7 — 495 — 939 30 31 |