Литература, рекомендуемая для изучения темы 1 Лаллеман Ж. Полугруппы и комбинаторные приложения. – М.: Мир,

1985.

2Лидл Р., Пильц Г. Прикладная абстрактная алгебра. – Екатеринбург: Изд-во УрГУ, 1996.

3Клиффорд А., Престон Г. Алгебраическая теория полугрупп, Т. 1. –

М.: Мир, 1972.

Тема 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. Алгебры отношений и полугруппы преобразований

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

1 Изучить такие основополагающие понятия теории моделей, как язык узкого исчисления предикатов (УИП) и его интерпретация в моделях (/1/, с. 1361; /2/, с. 103-118; /3/, с. 4-9).

2 Рассмотреть понятие алгебры отношений и разобрать (без доказательства) основную теорему об алгебрах отношений (/3/, с. 10-15).

3 Изучить метод определяющих пар в теории представления полугрупп преобразованиями и получить с его помощью абстрактную характеристику упорядоченных полугрупп преобразований (/3/, с. 15-30).

Восстановить доказательства всех примеров из указанных выше литературных источников.

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

1Кейслер Г., Чен Ч.Ч. Теория моделей. – М.: Мир, 1977.

2Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука,

1979.

3 Шайн Б.М. Лекции о полугруппах преобразований. – Саратов: Изд-во СГУ, 1970.

Тема 70. Рациональные языки

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

1Изучить основные понятия теории конечных автоматов (/1/, с. 174-178; /2/, с. 447-453, 483-486).

2Рассмотреть понятие полугруппы слов и понятие языка, распознаваемого конечным автоматом, исследовать взаимосвязь таких языков с конгруэнциями и фактор-полугруппами полугруппы слов (/1/, с. 178-184; /2/, с. 520-521).

3Разобрать понятие рационального языка и доказать теорему Клини об эквивалентности этого понятия понятию языка, распознаваемого конечным автоматом (/1/, с. 189-194).

Решить задачи 1-5 из упражнений на стр. 212 книги /1/.

Литература, рекомендуемая для изучения темы 1 Лаллеман Ж. Полугруппы и комбинаторные приложения. – М.: Мир,

1985.

2 Лидл Р., Пильц Г. Прикладная абстрактная алгебра. – Екатеринбург: Изд-во УрГУ, 1996.

Тема 71. Соответствие Эйленберга

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

1 Изучить основные понятия теории конечных автоматов и рассмотреть определение языка, распознаваемого конечным автоматом (/1/, с. 174-178; /2/, с. 447-453, 483-486).

2 Рассмотреть понятия синтаксической конгруэнции и синтаксического моноида, проанализировать их взаимосвязь с языками, распознаваемыми конечными автоматами (/1/, с. 178-184, 200-204; /2/, с. 520-521).

3 Разобрать понятия многообразия (или потока) языков и псевдомногообразия (или потока) конечных моноидов, доказать теорему Эйленберга о взаимосвязи этих двух фундаментальных понятий (/1/, с. 204207).

4 Рассмотреть различные подходы к исследованию псевдомногообразий конечных моноидов (/1/, с. 208-211; /3/).

Решить задачи 5, 10-13, 15 из упражнений на стр. 213-214 книги /1/.

Литература, рекомендуемая для изучения темы 1 Лаллеман Ж. Полугруппы и комбинаторные приложения. – М.: Мир,

1985.

2Лидл Р., Пильц Г. Прикладная абстрактная алгебра. – Екатеринбург: Изд-во УрГУ, 1996.

3Almeida J. On pseudovarieties, varieties of languages, filters of

congruences, pseudoidentities and related topics // Algebra Universalis, 27 (1990). P. 333-350.

Тема 72. Отношения Грина

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

1 Рассмотреть такие важные понятия теории полугрупп, как полугруппа преобразований и идеалы полугрупп, доказать основные свойства идеалов конечных полугрупп (/1/, с. 21-22, 35-42; /2/, с. 15-23).

2 Изучить определения и свойства отношений Грина на конечной полугруппе (/1/, с. 42-45; /2/, с. 72-77).

3 Рассмотреть приложения отношений Грина к описанию локального строения конечных полугрупп (/1/, с. 45-49).

4 Разобрать понятие группы Шютценберже D-класса конечной полугруппы и доказать ее свойства (/1/, с. 49-56; /2/, с. 93-96).

Решить задачи 1, 3, 5, 7-9, 13 из упражнений на стр. 70-71 книги /1/.

Литература, рекомендуемая для изучения темы 1 Лаллеман Ж. Полугруппы и комбинаторные приложения. – М.: Мир,

1985.

2 Клиффорд А., Престон Г. Алгебраическая теория полугрупп, Т. 1. –

М.: Мир, 1972.

Тема 73. Декомпозиция конечных моноидов

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

1 Изучить такие основные понятия теории групп, как композиционный ряд группы, полупрямое произведение групп и сплетение групп, доказать их основные свойства (/1/, с. 101-106; /2/, с. 468-472; /3/, с. 34-36, 65).

2 Рассмотреть понятие декомпозиции конечных моноидов и доказать основную теорему декомпозиции (/1/, с. 107-114).

3 Доказать теорему декомпозиции конечных моноидов преобразований

(/1/, с. 111-121).

Решить задачи 1, 5, 7, 12 из упражнений на стр. 122-123 книги /1/.

Литература, рекомендуемая для изучения темы 1 Лаллеман Ж. Полугруппы и комбинаторные приложения. – М.: Мир,

1985.

Тема 74. Рациональные и алгебраические языки над полукольцами

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

1 Рассмотреть полукольцо степенных рядов над произвольным полукольцом и доказать его полноту относительно канонически определенной на нем нормы (/1/, с. 131-132, 308-309).