Тема 68. Логика на словах

Один из основных подходов к исследованию распознаваемых языков базируется на известной теореме Ж. Бучи о характеризации регулярных языков средствами монадической логики второго порядка. В курсовой работе необходимо изучить метод исследования распознаваемых языков, основанный на монадической логике второго порядка. Рекомендуется следующий план работы.

1 Изучить основные понятия монадической логики второго порядка (/1/,

с. 328-330; /2/, с. 313-321; /3/, с. 1-2).

2 Рассмотреть приложение монадической логики второго порядка к теории языков (/2/, с. 321-324; /3/, с. 1-2).

3 Разобрать доказательство теоремы Ж.Бучи о характеризации регулярных языков средствами монадической логики второго порядка (/2/, с. 325-329; /3/, с. 1-2).

4 С помощью теоремы Ж.Бучи исследовать взаимосвязь между иерархиями языков и определяющих их формул логики первого порядка (/2/, с. 329-338; /3/, с. 8-13).

Разобрать все примеры из указанных выше литературных источников и решить задачи 2, 3, 6-8 из упражнения на с. 352 в /2/.

Литература, рекомендуемая для изучения темы

1Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

2Pin J.-E., Perrin D. Infinite words. 2001 (в печати, текст доступен на www.liafa.jussieu.fr/~jep/Resumes/InfiniteWords.html).

3Pin J.-E. Logic on Words. Report LITP 94/53, Institut Blaise Pascal, 1994 (препринт).

Тема 69. Алгебры отношений и полугруппы преобразований

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