Интерпретационные методы в теории алгоритмических алгебр

• Автор: Суржко, Сергей Васильевич
• Шифр специальности: 01.03.01
• Научная степень: Докторская
• Год защиты: 1996
• Место защиты: Киев
• Количество страниц: 197 с.

- 2 -СОДЕРЖАНИЕ
Введение
Глава 1. Алгебры 0-алгоритмов и свободны© алгоритмические алгебры
1. Основные определения
1.1. Недетерминированные операторы. - Алгебра
0-алгоритмов
1.2. Алгебра недетерминированных алгоритмов
1.3. Алгебра детерминированных алгоритмов
2 . Редукты алгебры 0-алгоритмов
3. 0 -языки
4. Свободные алгебры 0-алгоритмов. Связь
с алгеброй Клини
5. Свободные алгебры детерминированных алгоритмов
6. Свободные алгебры недетерминированных алгоритмов
Глава 2. Формальные языки с интерпретацией алфавита в булевой алгебре
1. Вводные определения
2. Верхняя полурешетка и и ее свойства
3. Связь с конечными автоматами
4. Регулярные языки над интерпретированным алфавитом
5. Алгоритмические проблемы
6. Классификация языков над интерпретированным алфавитом
7. Разрешимость проблемы тождества в свободных алгебрах недетерминированных алгоритмов

Глава 3. Сетевые динамические модели регулярных схем операторов
1. Генераторы дискретных процессов (ГДП). Основные определения
2. Связь с сетями Петри
3. Свободные ГДП
4. Связь с частично коммутативными моноидами и
языками следов
5. Полугрупповые свойства свободного языка ГДП
6. Многоуровневое представление ГДП
7. Многоуровневые алгоритмические системы. Представление регулярных схем операторов в виде ГДП
8. Организация вычисления значений оператора алгоритмической алгебры, заданного ГДП
Глава 4. Специальные классы алгоритмических алгебр. Некоторые приложения
1. Регулярные схемы над памятью. Связь с дискретными преобразователями
2. Вероятностью оценки алгоритмических процессов. Марковские алгоритмические алгебры
3. Некоторые приложения
3.1. Моделирование и анализ системы управления предприятием
3.2. Декомпозиция информационного фонда
на базы данных
Заключение
Список литературы
Приложение
ВВЕДЕНИЕ
Одной из определяющих тенденций развития науки является ее математизация, охватывающая, в частности, теорию компьютерных вычислений, в том числе теоретическое программирование. В этой связи особо следует отметить интенсивное проникновение в компьютерную науку идей и методов дискретной математики, алгебры и математической логики, успешное применение теории автоматов, формальных языков и грамматик как для сугубо теоретических, так и для практических целей, в частности, разработки систем программирования, основанных на языках высокого и сверхвысокого уровня, развитие средств логического программирования и т.д.
Особый вклад в развитие данной проблематики вносит алгебраический аппарат, на основе которого создан целый ряд теоретических и практических работ, среди которых особое место занимают работы, связанные с исследованием и применением идей теории алгоритмических алгебр. Основным объектом данной теории является универсальная алгебра алгоритмов той или иной сигнатуры, операции которой моделируют различные программистские конструкции, а целью -исследование математических свойств данной алгебры и связанных с ней объектов, в частности, установление взаимосвязей этих объектов с другими разделами математики и математической кибернетики.
Основы данной теории была заложены В.М.Глушковым в работах [17, 18], в которых впервые было введено и исследовано понятие алгоритмической алгебры (иначе - алгебры алгоритмов или системы алгоритмических алгебр). На основе этого понятия В.М.Глушковым и его учениками и последователями был получен целый ряд результатов
Слова их, и2 є Б назовем дизъюнктными, если АЫг) = А(и2),
В (В (и2) . В этом случае пишем и1йи2
Рассмотрим множество сг-слов Б„ = (о(и) : и є Б) и построим свободную полугруппу Бп* (над образующими Б0) с нулем 0. Зададим на Зо* определяющие соотношения М такого вида (здесь и2 є Б) :
о(и1)ст(и2) = аЫг)о{»1) ; (1.1)
о(Иі)ст(и2) = аЫх), если и2 = рг Их; (1.2)
<т(Их)ст(и2) = 0 , если существуют такие слова Чх = рг Их, у2 * рг и2, что vxdv2. (1.3)
Заметим, что соотношения (1.1)-(1.3) выполняются тогда и только тогда, когда все записанные равенства соответствуют функциональной эквивалентности ст-слов.
Коммутативную полугруппу, заданную копредставлением <БП; М> , обозначим через Бв# . Из ее определения следует, что умножение индуцирует в Б с* частичный порядок, являющийся естественным продолжением такого упорядочения элементов Б„ : о(Их) < а(иг) если выполняется условие (1.2).
Канонической формой ненулевого элемента из Б„# назовем конечное произведение вида сг(их)о(и2) ..о(ип) , определяемое с точностью до перестановки сомножителей, где все элементы о (Их) , о(и2), ... , сг(ип) е Б0 попарно несравнимы между собой. Канонической формой нулевого элемента из Б0* называем 0.