Введение
1.1. Проблема эквивалентности программ 5
1.2. Теория схем программ 7
1.3. Быстрые алгоритмы проверки эквивалентности 11
1.4. Результаты исследования 13
1.5. Новизна полученных результатов 18
1.5.1. Последовательные программы 18
1.5.2. Унарные рекурсивные программы 20
1.6. Структура работы 21
Глава 2. Общие понятия и обозначения 23
2.1. Последовательности, слова 23
2.2. Порядки 25
2.3. Автоматы 26
2.4. Моноиды 27
2.5. Коммутативность и подавление 29
Глава 3. Модели программ 31
3.1. Пропозициональные последовательные программы 31
3.1.1. Синтаксис 32
3.1.2. Интерпретации 34
3.1.3. Реализуемость трасс в интерпретации 37
3.1.4. Эквивалентность и совместность 38
3.1.5. Утверждения 38
3.2. Унарные рекурсивные программы 39
3.2.1. Синтаксис 40
3.2.2. Реализуемость трасс в интерпретации 43
3.2.3. Эквивалентность и совместность 43
3.2.4. Линейность и металинейность 44
3.2.5. Классификация заголовков 45
3.2.6. Нормальная форма 46
3.2.7. Утверждения 47
Глава 4. Формулировка результатов и методология исследования программ 48
4.1. Формулировка результатов 48
4.2. Метод совместных вычислений 49
Глава 5. Эквивалентность пропозициональных последовательных программ на шкалах с коммутативностью и подавлением 54
5.1. Упорядоченность моноидов с коммутативностью и подавлением . 56
5.2. Основные свойства упорядоченных моноидов с коммутативностью и подавлением 59
5.3. Распознавание подавления операторов 68
5.4. Граф совместных вычислений 77
5.5. Эффекты подавления 84
5.6. Ограничение числа вершин графа совместных вычислений . 92
5.7. Полиномиальная разрешимость проблемы эквивалентности . 103
Глава 6. Эквивалентность линейных унарных рекурсивных программ на упорядоченных полу групповых шкалах 108
6.1. Критериальные системы 109
6.2. Граф совместных вычислений 113
6.3. Разрешимость проблемы эквивалентности 119
6.4. Полиномиальная разрешимость проблемы эквивалентности 129
Глава 7. Сильная эквивалентность металинейных унарных рекурсивных программ 134
7.1. Вспомогательные понятия и утверждения 135
7.2. Граф совместных вычислений 138
7.3. Ограничение числа вершин графа совместных вычислений 147
7.4. Полиномиальная разрешимость проблемы эквивалентности 149
Глава 8. Заключение 152
Список литературы
