Geum.ru

Программы и учебный план отделения теоретической и прикладной лингвистики Издательство Московского университета 2009

Вид материалаДокументы
Подобный материал:
1   ...   47   48   49   50   51   52   53   54   55

5. Постовские системы соответствия.


5.1. Полутуэвская продукция, система. Проблема слов для полутуэвской системы. Сведение проблемы остановки к проблеме слов некоторой полутуэвской системы. Существование полутуэвской системы с неразрешимой проблемой слов.

5.2. Постовская система соответствия, решение этой системы. Построение по полутуэвской системе S и паре p слов над ее алфавитом постовской системы соответствия, имеющей решение тогда и только тогда, когда в S выводима p. Неразрешимость проблемы распознавания существования решения постовской системы соответствия.

6. Алгоритмические проблемы, связанные с порождающими грамматиками.


6.1. Распознаваемость в классе контекстных грамматик проблемы выводимости слова. Распознаваемость в классе контекстно-свободных грамматик проблемы выводимости слова, проблемы непустоты языка, проблемы бесконечности языка. Распознаваемость в классе автоматных грамматик проблемы включения языков.

6.2. Построение по постовской системе P соответствия пары контекстно-свободных языков, тогда и только тогда имеющих непустое пересечение, когда P имеет решение. Нераспознаваемость в классе контекстно-свободных грамматик проблемы непустоты пересечения языков, проблемы бесконечности пересечения языков, проблемы полноты языка, проблемы равенства языков, проблемы бесконечности дополнения языка, проблемы автоматности языка, проблемы контекстно-свободности пересечения языков, проблемы контекстно-свободности дополнения языка. Нераспознаваемость проблемы неоднозначности контекстно-свободной грамматики.

7. Сложность вычисления и сложность описания.


7.1. Меры сложности вычислений. Существование сколь угодно сложно вычислимых функций. Теорема об ускорении. Классы сложности. Теорема о пробелах.

7.2. Алгоритмический подход к понятию количества информации. Сложность конечного объекта. Теорема Колмогорова о существовании оптимального способа описания.

7.3. Полиномиальные алгоритмы и класс P. Недетерминированные вычисления и класс NP. Понятие NP-полной задачи. NP-полнота задач о выполнимости, о существовании гамильтонова цикла, о коммивояжере, о разбиении.

8. Категориальные грамматики.


Базисные категориальные грамматики. Исчисление Айдукеви-
ча — Бар-Хиллела. Описание фрагмента английского языка с помощью категориальной грамматики.

9. Исчисление Ламбека.


9.1. Синтаксическое исчисление Ламбека, примеры выводов в нем. Категориальные грамматики Ламбека. Теоремы об устранимости сечения, об интерполяционном свойстве исчисления Ламбека. Интерпретация исчисления Ламбека в полугруппе подмножеств свободной полугруппы, теорема о корректности, теорема о полноте исчисления Ламбека. Интерпретация исчисления Ламбека в свободной группе.

9.2. Теорема о совпадении класса контекстно-свободных языков с классом языков, распознаваемых грамматиками Ламбека.

10. Семантика Монтегю.


10.1. Язык интенсиональной логики, его интерпретации. Временные и модальные логики первого порядка. Принцип ламбда-конверсии в интенсиональной логике.

10.2. Соответствие между грамматическими категориями естественного языка и типами языка интенсиональной логики. Общие принципы перевода фрагментов естественного языка на язык интенсиональной логики. Особенности перевода выражений отдельных грамматических категорий на язык интенсиональных логик. Применение языка интенсиональной логики для исследования логических связей между предложениями естественного языка.

литература

Обязательная литература


Гинзбург С. Математическая теория контекстно-свободных языков. М., 1970. [С. 19–26, 41–108, 120–130, 164–185.]

Гладкий А. В., Мельчук И. А. Элементы математической лингвистики. М., 1969. [С. 122–150, 177–182.]

Гросс М., Лантен А. Теория формальных грамматик. М., 1971. [С. 112–138, 143–155, 159–171, 194–199.]

Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М., 1982. [С. 13–57, 64–84.]

Ламбек И. Математическое исследование структуры предложения // Математическая лингвистика: Сборник переводов / Шрейдер Ю. А. и др. (ред.). М., 1964. [С. 47–68.]

Логический подход к искусственному интеллекту: От модальной логики к логике баз данных / Тейз А., Грибомон П., Юлен Г. и др. (ред.). М., 1998. [С. 85–209.]

Саломаа А. Жемчужины теории формальных языков. М., 1986. [С. 24–38.]

Дополнительная литература


Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., 1979. [С. 354–363, 404–440.]

Гладкий А. В. Формальные грамматики и языки. М., 1973. [С. 17–39, 79–89, 115–130, 157–168, 185–199.]

Кук Д., Бейз Г. Компьютерная математика. М., 1990. [С. 257–343.]

Лаллеман Ж. Полугруппы и комбинаторные приложения. М., 1985. [С. 15–16, 174–180, 293–301, 304–308, 330.]

Логический подход к искусственному интеллекту: От классической логики к логическому программированию / Тейз А., Грибомон П., Луи Ж. и др. (ред.). М., 1990.
[С. 266–314.]

Carpenter B. Type-logical semantics. The MIT Press, 1997. [С. 37–176.]

Dowty D. R., Wall R. E. and Peters S. Introduction to montague semantics. Kluwer, 1992.

Janssen T. M. V. Foundations and applications of Montague grammar. Amsterdam, 1986.

Sipser M. Introduction to the theory of computation. PWS Publishing company, 1997.
[С. 29–122, 223–294.]

Программу составили Е. Ю. Ногина, М. Р. Пентус, В. Е. Плиско