Интерпретационные методы в теории алгоритмических алгебр тема диссертации и автореферата по ВАК РФ 01.03.01, доктор физико-математических наук Суржко, Сергей Васильевич

• Суржко, Сергей Васильевич
• доктор физико-математических наук
• 1996

Оглавление диссертации доктор физико-математических наук Суржко, Сергей Васильевич

СОДЕРЖАНИЕ

Введение

Глава 1. Алгебры 0-алгоритмов и свободные алгоритмические алгебры

1. Основные определения

1.1. Недетерминированные операторы.- Алгебра

П-алгоритмов

1.2. Алгебра недетерминированных алгоритмов

1.3. Алгебра детерминированных алгоритмов

2. Редукты алгебры О-алгоритмов

3. П-языки

4. Свободные алгебры П-алгоритмов. Связь

с алгеброй Клини

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], в которых впервые было введено и исследовано понятие алгоритмической алгебры (иначе - алгебры алгоритмов или системы алгоритмических алгебр), На основе этого понятия В.М.Глушковым и его учениками и последователями был получен целый ряд результатов

как теоретического, так и прикладного характера (см., в частности, работы [19-22, 27, 30- 33, 35, 43-46, 56, 105-110, 112-115]). Отметим лишь некоторые из результатов, которые имеют наиболее тесную связь с данной диссертационной работой.

Одним из основных результатов теории алгоритмических алгебр следует считать теорему В'.М.Глушкова о том, что функционирование конечного дискретного преобразователя (взаимодействующих автоматов, управляющего и операционного) может быть описано регулярной схемой оператора алгоритмической алгебры, однозначно определяемой по данному преобразователю [18]. Этот результат указывает, в частности, на тесную взаимосвязь алгоритмических проблем, формулируемых для алгоритмических алгебр, с проблемами эквивалентности дискретных преобразователей. A.A.Летичевским был получен ряд результатов по алгоритмической разрешимости проблемы эквивалентности автоматов относительно полугрупп [43-45]. Разрешимость алгоритмической проблемы тождества слов и существование полной системы аксиом для специального класса алгебр алгоритмов (алгебр с замкнутыми условиями или S-алгебр) была установлена Г.Е.Цейтлиным в работе [107]. Аналогичный результат для специального класса алгебр недетерминированных алгоритмов (S(Н)-алгебр) был получен Ю.А.Ющенко [115]. А.А.Летичевским была установлена связь алгоритмических алгебр с теорией схем программ [40], что позволило рассматривать проблематику алгебр алгоритмов в общем контексте теории дискретных систем [31] . В работах [12, 4 6, 105] рассмотрены алгебры структур данных и их связь с проблемами проектирования программ.

Важным этапом в развитии теории и приложений алгоритмических алгебр явилось издание монографии В.М. ГЛушкова, Г.Е. Цейтлина,

E.JI. Ющенко "Алгебра. Языки. Программирование" (Киев: Наук, думка, 1974. - 328 е.; 2-е изд., перераб., 1978. - 320 е.; 3-е изд., перераб. и доп., 1989. - 376 е.; Berlin: Acad.-Verl., 1980, -322 s,), посвященной фундаментальным исследованиям, связанным с применением аппарата общей алгебры в программировании.

Сфера приложений теории алгоритмических алгебр чрезвычайно обширна и охватывает параллельную обработку данных на многопроцессорных машинных комплексах [7, 20, 33], проектирование вычислительных систем [30], проектирование и синтез схем программ'[109-110, 112-113], анализ и оптимизацию схем программ [106], структуры данных [105], специализированные системы автоматизированного проектирования [111, 113], формы представления знаний [108], моделирование технологических процессов [3, 4, 111], а также'ряд других проблем специального характера. Эти приложения опираются и, в свою очередь, стимулируют такие теоретические исследования, которые призваны объяснить процессы, задаваемые регулярными схемами операторов и условий алгоритмических алгебр, а также сделать их исследование эффективным.

Следует заметить, что одной из основных задач, с необходимостью решения которых связано возникновение алгоритмических алгебр, являлась задача эквивалентных преобразований микропрограмм (регулярных схем)[17], которая удовлетворительным образом не решена до сих пор. Поэтому весьма актуальным является исследование алгоритмических проблем тождества для тех или иных классов алгебр алгоритмов.

Теорема В.М.Глушкова о представлении дискретных преобразователей регулярными схемами устанавливает возможность (и способ) формального описания вычислений, задаваемых вычислительным

устройством (дискретным преобразователем) в алгебраических терминах. Вместе с тем, обратное утверждение для рассмотренного класса преобразователей не имеет места. Поэтому актуальными являются задачи построения таких классов дискретных преобразователей, в котором указанная теорема не только верна, но и допускает обращение. Не менее важными являются задачи теоретического исследования способов организации последовательных и параллельных вычислений, задаваемых регулярными схемами операторов и обладающих теми или иными полезными в практическом отношении свойствами.

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

Объектом исследования в диссертации являются алгебры (детерминированных и недетерминированных) алгоритмов и связанные с ними объекты.

Целью диссертационной работы является разработка и применение интерпретационных методов исследования алгоритмических алгебр.

Для достижения цели исследования в диссертации решены следующие задачи:

- разработан метод редукции алгебр детерминированных и недетерминированных алгоритмов к единому, более простому объекту -

алгебре П-алгоритмов;

- введено и исследовано понятие О.-языка, обобщающее формальный язык, разработан метод изучения £2-языков путем их сведения к унифицированным объектам, так называемым точным П-языкам;

- введены понятия и разработан метод исследования свободных алгебр й-алгоритмов, детерминированных и недетерминированных алгоритмов, основанный на точных П-языках;

- разработан общий метод исследования специального класса П-языков - формальных языков над алфавитом, интерпретированным в булевой алгебре;

- разработан метод изучения регулярных языков над алфавитом, интерпретированным в булевой алгебре, в том числе алгоритм проверки таких языков на совпадение;

- разработан метод классификации языков над алфавитом, интерпретированным в булевой алгебре;

- разработан аппарат динамических сетевых моделей специального вида (генераторов дискретных процессов, ГДП) и, на его

основе, - метод моделирования регулярных схем операторов алгоритмических алгебр в виде ГДП;

- разработан метод многоуровневого представления алгоритмических алгебр;

- разработаны методы формального описания дискретных преобразователей в терминах регулярных схем (с настройкой) операторов алгоритмических алгебр;

- разработан метод исследования случайных вычислительных процессов, задаваемых однородными цепями Маркова с конечным числом состояний, интерпретируемых как элементы марковской алгоритмической алгебры - стохастического аналога алгебры алгоритмов.

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

Научная новизна полученных результатов состоит в следующем.

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

более простого объекта - алгебры О-алгоритМов, введенной в работе и однозначно задаваемой по исходной алгоритмической алгебре. Любая алгебра (детерминированных или недетерминированных) алгоритмов может быть построена по некоторой алгебре П-алгоритмов с помощью стандартной конструктивной процедуры.

2. Введены и исследованы понятия П-языка и точного О-языка, обобщающие понятие формального языка и допускающие интерпретацию в классе частичных точечно-множественных (недетерминированных) операторов. На основе этих понятий введены и исследованы свободные

алгебры П-алгоритмов, детерминированных и недетерминированных .

алгоритмов. Частным случаем свободной алгебры О-алгоритмов является алгебра регулярных выражений (алгебра Клини). Установлены свойства (точных) П-языков, задаваемых регулярными схемами свободных алгебр детерминированных и недетерминированных алгоритмов.

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

4. Установлена связь рациональных (регулярных) языков над алфавитом, интерпретированным в булевой алгебре, с конечными автоматами. Получено обобщение на данный случай теоремы Клини о представлении рациональных языков автоматами. Доказана разрешимость алгоритмической проблемы тождества для регулярных языков над алфавитом, интерпретированным в булевой алгебре.

5. Установлена разрешимость алгоритмической проблемы тождества регулярных схем (операторов и условий) свободных алгебр недетерминированных алгоритмов.

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

7. Установлена возможность представления регулярной схемы оператора алгоритмической алгебры в виде динамической сетевой модели (ГДП), вычисляющей тот же оператор. На основе данного

представления получена возможность организации вычислений, устойчивых к "сбоям" гипотетической машины.

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

Практическая ценность и реализация работы. В работе построен метод, позволяющий реализовать алгебры детерминированных и недетерминированных алгоритмов, сигнатура которых включает соответственно семь и восемь операций {без учета нульарных операций) средствами существенно более простой алгебры О-алгоритмов с четырьмя операциями. Такой подход упрощает разработку программных средств, ориентированных на представление алгоритмов и программ в виде регулярных схем алгоритмических алгебр.

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

Аппарат марковских алгоритмических алгебр позволяет эффективно решать ряд практических задач вероятностного характера, относящихся к программным вычислениям, в частности, вероятностный аналог задачи тестирования программ.

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

На основе полученных результатов при непосредственном участии автора были разработаны программные средства моделирования и

анализа интегрированной системы управления дискретным производством ПАРИС и АВАНС, а также пакет прикладных программ "Декомпозиция информационной базы" (Отраслевой фонд алгоритмов и программ АСУ Минприбора СССР, инв.№ 1030, Калинин, Центрпрограммсистем, 1983), реализующий описанный в диссертации метод декомпозиции информационного фонда на базы данных.

Системы ПАРИС и АВАНС были апробированы на реальных данных, относящихся к трем подсистемам интегрированной АСУ НПО "Электрон" (системы автоматизированного проектирования изделий, системы оперативно-производственного планирования, автоматизированной системы оперативно-диспетчерского управления). Результаты моделирования были обработаны, и на их основе разработаны конкретные рекомендации для повышения эффективности системы управления Львовского научно-производственного объединения "Электрон".

Разработка и апробация указанных программных средств проводилась в рамках следующих опытно-конструкторских и научно-исследовательских работ: ОКР "Разработка общесистемных и функциональных средств автоматизации управления производственным объединением" (шифр "Меркурий 2.2", номер государственной регистрации У45449 от 04.05.87 г.), проведенной на основании приказов Министерства промышленности средств связи СССР № 547 дсп от 16.12.85 г. и № 96 дсп от 21.03.86 г.; НИР "Разработка принципов построения типовых инструментальных и функциональных средств- интегрированных АСУ предприятием (объединением) " (шифр "Старт", номер государственной регистрации У48996 от 06.05.88 г.), проведенной на основании Постановления Государственной Комиссии

Совета Министров СССР № 47 от 11.02.88 г. и приказа Министерства промышленности средств связи СССР № 61 от 19.02.88 г.; НИР "Проведение научных исследований по направлению развития работ в области АСУ предприятия, объединения, создание научно-технического задела по разработке технико-экономических решений для повышения уровня интеграции и эффективности указанных систем в ХШ-й пятилетке" (шифр "Развитие", номер государственной регистрации У56580 от 15.03.89 г.), проведенной по решению Государственной Комиссии Совета Министров СССР № 47 от 11.02.88 г. и приказу Министерства промышленности средств связи СССР № 61 от 19.02.88 г.; при выполнении технического задания по научно-технической программе ГКНТ СССР 0.80.02, задание 35.01.06Д "Разработать методологические и инструментальные средства для автоматизированного проектирования сложных многоуровневых и крупномасштабных систем". Система ПАРИС (версия 1.1) отмечена серебряной медалью ВДНХ СССР.

Основные положения диссертации отражены в публикациях [52-55, 61-66, 71-100, 114].

Основной текст диссертационной работы состоит из четырех глав, охватывающих двадцать четыре раздела.

В первой главе диссертации алгебры детерминированных и недетерминированных алгоритмов рассматриваются с точки зрения более "простого" объекта - вводимой в данной главе универсальной алгебры О-алгоритмов. Сигнатура алгебры ¿^-алгоритмов содержит лишь четыре операции, три из которых (сложение, умножение и итерация) представляют собой хорошо известные операции алгебры Клини.

Показано, что изучение алгебраических свойств алгоритмических . алгебр (детерминированных и недетерминированных алгоритмов) может быть сведено к изучению алгебры О-алгоритмов. Именно, показывается, что упомянутые алгебры алгоритмов являются редуктами алгебры £)-алгоритмов, конечная система порождающих которой однозначно определяется порождающими алгоритмической алгебры. При этом информационные множества алгебры алгоритмов и соответствующей алгебры ^-алгоритмов совпадают. Прямая и обратная процедуры сопоставления алгоритмической алгебре соответствующего редукта алгебры П-алго-ритмов, описанные в данной главе, составляют сущность метода редукции алгоритмических алгебр. Вводятся и исследуются свободные алгебры П-алгоритмов, которые можно рассматривать как фактор-алгебры алгебры термов заданной сигнатуры. Этими термами однозначно определяются специального рода объекты - так называемые

0-языки. При этом П-языки, определяемые регулярными выражениями алгебры Клини, совпадают с обычными рациональными языками. Поэтому рассматриваемая алгебра является некоторым обобщением алгебры

Клини. Показывается, что каждый элемент свободной алгебры П-алго-ритмов задает единственный ^-язык специального вида, так называемый точный П-язык. На основе понятия свободной алгебры П-алгорит-мов вводятся и исследуются понятия свободных алгебр детерминированных и недетерминированных алгоритмов. Соответствующие определения "свободны" от операторной терминологии, т.е. не используют понятий информационного множества, оператора и условия, и свойства свободных алгоритмических алгебр определяются свойствами точных языков. Вместе с тем любая алгебра (детерминированных или недетер-

минированных) алгоритмов является гомоморфным образом некоторой свободной алгебры.

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

Примером точного П-языка является формальный язык, рассматриваемый над таким алфавитом, части символов которого взаимнооднозначным образом сопоставлены элементы некоторой конечной булевой алгебры, и называемый языком с интерпретацией алфавита в булевой алгебре. Подобные языки возникали и рассматривались ранее в связи с изучением алгебр детерминированных и недетерминированных алгоритмов (конфигурации в [107]), схем программ (цепочки стандартной схемы в [40]) а также в ряде других случаев. Формальное понятие языка над алфавитом с интерпретацией в булевой алгебре вводится и изучается во второй главе диссертационной работы. Показывается, что свойства языков с интерпретированным в булевой алгебре алфавитом определяются свойствами некоторой однозначно определяемой по исходному алфавиту и булевой алгебре алгебраической системе и. Сигнатура операций алгебраической системы и включает сложение, умножение и итерацию, а сигнатура отношений этой системы состоит из единственного отношения -согласованного с операциями частичного порядка, относительно которого и является верхней полурешеткой. Исследуются свойства алгебраической системы и, определяемые языками специального вида, построенными над алфавитом, часть символов которого соответствует элементам конечного разбиения единицы булевой алгебры. Устанавливается связь этих языков с абстрактными автоматами, что

приводит к некоторому обобщению теоремы Клини о совпадении классов рациональных и регулярных (задаваемых конечными автоматами) языков. Основное внимание в данной главе уделяется регулярным языкам с интерпретацией алфавита. Исследуются их свойства и доказывается разрешимость проблемы тождества для таких регулярных языков, заданных конечными автоматами или же регулярными выражениями алгебры Клини. На основе полученных результатов доказана разрешимость проблемы тождества для свободной алгебры недетерминированных алгоритмов. Изучается возможность классификации языков с интерпретацией алфавита по аналогии с классификацией Хомского формальных языков. Доказана возможность подхода, основанного на данной классификации.

В третьей главе диссертации разрабатывается и применяется к исследованию регулярных схем операторов алгоритмических алгебр аппарат динамических сетевых моделей - генераторов дискретных процессов (ГДП). Статическая структура ГДП может рассматриваться как вычислительная модель Тыугу, а правила функционирования носят весьма общий характер и задают недетерминированное поведение системы. Исследуются выразительные возможности введенной модели, показывается, что в терминах ГДП могут быть описаны автоматы и сети Петри. Вводятся и изучаются специальные классы ГДП (свободные ГДП, ГДП с настройкой). Установлена связь ГДП с частично коммутативными моноидами и теорией следов, исследуются формальные языки, порождаемые ГДП, изучаются полугрупповые свойства этих языков. Рассматривается многоуровневое представление ГДП. Вводится понятие многоуровневой алгоритмической системы. Показывается, что регулярная схема оператора алгоритмической алгебры допускает разложение по некоторой многоуровневой алгоритмической системе (т.е. регуляр-

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

В четвертой главе диссертационной работы рассмотрены специальные классы алгоритмических алгебр и некоторые приложения введенного в предшествующих разделах аппарата к объектам, выходящим за рамки теории алгоритмических алгебр. Изучаются регулярные схемы над памятью, определение которых дается по аналогии со схемами над памятью, рассматриваемыми в [30]. Показано, что оператор, заданный конечным дискретным преобразователем, можно задать регулярной схемой с настройкой в такой алгоритмической алгебре, сигнатура которой содержит лишь две операции - а-итерацию и

композицию операторов, а множество элементарных условий состоит из единственного условия. Доказывается, что оператор, задаваемый ГДП с настройкой, может быть представлен регулярной схемой (с настройкой) оператора алгоритмической алгебры, сигнатура которой содержит три операции - композицию, а-дизъюнкцию и недетерминированную дизъюнкцию операторов. Установлено, что для любой регулярной схемы оператора алгебры недетерминированных алгоритмов существует такая регулярная схема (с настройкой) алгебры алгоритмов с двумя операциями (недетерминированной дизъюнкцией и а-итерацией), элементарные операторы которой определяются по исходной схеме, вычисляющая тот же оператор. Из сформулированных результатов, в частности, следует, что класс ГДП представляет собой такой класс дискретных преобразователей, в котором теорема Глушкова (о представлении оператора, заданного конечным дискретным преобразователем, регулярной схемой) допускает обращение. Вводится и исследуется понятие марковской алгоритмической системы, которая дает возможность описания однородных Цепей Маркова с конечным числом состояний в терминах, аналогичных алгебро-алгоритмическим. Доказано, что марковская алгоритмическая система является гомоморфным образом алгоритмической алгебры. С помощью введенного понятия решаются задачи вероятностного характера применительно к моделям, заданным в виде регулярных схем операторов. К числу таких задач относятся: определение вероятности того, что значение оператора, представленного регулярной схемой и вычисляемого в случайно выбираемой точке, удовлетворяет заданному условию (вероятностный аналог задачи тестирования); определение вероятности прерывания вычислений до их завершения (переход системы в заданное поглощающее состояние); определение математического ожидания времени, прове-

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

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

- го -

Заключение диссертации по теме «Астрометрия и небесная механика», Суржко, Сергей Васильевич

ЗАКЛЮЧЕНИЕ

В диссертации предлагается для решения актуальной научной проблемы исследования алгебр детерминированных и недетерминированных алгоритмов использовать интерпретационные методы, основанные на сведении данных алгебр и связанных с ними формальных объектов к другим объектам, исследование которых может быть выполнено достаточно эффективным образом. К числу указанных объектов, введенных и рассмотренных в диссертации, относятся универсальные алгебры П-алгоритмов, формальные языки над интерпретированным в булевой алгебре алфавитом, генераторы дискретных процессов, марковские алгоритмические алгебры.

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

В работе получены следующие результаты, обладающие новизной и выносимые на защиту:

1. Разработан интерпретационный ме,тод, позволяющий свести алгебры детерминированных и недетерминированных алгоритмов к единому, существенно более простому объекту - введенной и исследованной в работе алгебре П-алгоритмов. Показано, что свойства любой алгебры детерминированных или недетерминированных алгоритмов определяются свойствами алгебры П-алгоритмов, однозначно задаваемой по исходной алгоритмической алгебре. Любая алгебра (детерминированных или недетерминированных) алгоритмов может быть построена по некоторой алгебре П-алгоритмов с помощью стандартной конструктивной процедуры.

2. Введены и исследованы понятия П-языка и точного П-языка, а на основе этих понятий - свободные алгебры П-алгоритмов, детерминированных и недетерминированных алгоритмов. Установлена связь свободной алгебры П-алгоритмов и свободной алгебры недетерминированных алгоритмов с алгеброй Клини. Разработан метод исследования свободных алгебр П-алгоритмов, детерминированных и недетерминированных алгоритмов, основанный на свойствах точных П-языков, задаваемых схемами соответствующих алгебр.

3. Введено понятие и разработан общий метод исследования специального класса П-языков - формальных языков над алфавитом, интерпретированным в булевой алгебре. Установлена возможность классификации таких языков по аналогии с классификацией Хомского.

4. Разработан метод исследования регулярных языков над алфавитом, интерпретированным в булевой алгебре. Установлена связь рациональных (регулярных) языков над алфавитом, интерпретированным в булевой алгебре, с конечными автоматами. Получено обобщение на данный случай теоремы Клини о представлении рациональных языков автоматами. Описан общий алгоритм, позволяющий проверить эквивалентность таких языков.

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

6. Установлена разрешимость алгоритмической проблемы тождества регулярных схем (операторов и условий) свободных алгебр недетерминированных алгоритмов.

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

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

9. Разработаны методы формального описания дискретных преобразователей в терминах регулярных схем (с настройкой) операторов алгоритмических алгебр.

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

11. На основе разработанных теоретических положений предложено использование введенного в работе аппарата для программного моделирования и анализа системы управления промышленным предприятием, а также для решения задачи декомпозиции информационного фонда предприятия на базы данных.

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

Список литературы диссертационного исследования доктор физико-математических наук Суржко, Сергей Васильевич, 1996 год

СПИСОК ЛИТЕРАТУРЫ

1. Абрамов С.А. Элементы анализа программ, - М.: Наука, 1986. - 128 с.

2. Агафонов В.Н. Спецификация программ: понятийные средства и их организация. - Новосибирск: Наука, 1987. - 340 с.

3. Акуловский В.Г. О проектировании программного обеспечения АСУ ТП в рамках метода МСПП//Кибернетика и системный - анализ. -1993. - N2. - С. 165-174.

4. Акуловский В.Г. Формализация проектирования программного обеспечения АСУ ТП в черной металлургии//Кибернетика и системный анализ. - 1991. - N5. - С. 138-145.

5. Алгебраическая теория автоматов, языков и полугрупп. - М. Статистика, 1975. - 335 с.

6. Андон А.Ф, Последовательные вычислительные граф-схемы и их реализация на ЭВМ. Препринт. - Киев: Ин-т кибернетики АН УССР. -1977. - 24 с.

7. Андон Ф.И. Мультипроцессорное интегрированное мультипрограммирование//Кибернетика. - 1982. - N5. - С. 41-45.

8. Андон Ф.И., Марьянчик A.M., Одинцова Л.Н., Тихоненко Л.А. Основные положения и архитектура системы реляционного манипулирования данными//Управляющие системы и машины. - 1986. -№2. - С. 35-42.

9. Анисимов A.B. Рекурсивные преобразователи информации. -Киев: Вища школа, 1987. - 231 с.

10. Анисимов A.B., Кулябко П.П. Программирование параллельных процессов в управляющих пространствах//Кибернетика. - 1984. - №3.

- С. 79-88.

11. Биркгоф Г. Теория решеток. - М.: Наука, 1984. - 566 с.

12. Бублик В. В», Гороховский С. С. Алгебраическая трактовка структур данных//Кибернетика. - 1978. - № 2. - С. 10-15.

13. Вальковский В.А, Распараллеливание алгоритмов и программ. Структурный подход. - М.: Радио и связь, 1989. - 174 с.

14. Вельбицкий И.В. Технология программирования. - Киев: Техника, 1984. - 279 с.

15. Владимиров Д.А. Булевы алгебры. - М.: Наука, 1969. -320 с.

16. Вулих В.З. Введение в теорию полуупорядоченных пространств. ~ М.: Физматгиз, 1961. - 407 с.

17. Глушков В.М. Теория автоматов и формальные преобразования микропрограмм//Кибернетика. - 1965. - N1. - С. 3-1I.

18. Глушков В.М., Летичевский A.A. Теория дискретных преобразователей//Избранные вопросы алгебры и логики. -Новосибирск: Наука, 1973. - С. 5-39.

19. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. - Киев: Наукова думка, 1989. - 376 с.

20. Глушков В.М., Цейтлин Г.Е., Шенко Е.Л. Методы символьной мультиобработки. - Киев: Наук.думка, 1980. - 252 с.

21. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Проблемы анализа и синтеза структурированных параллельных программ//Кибернетика. -1981. - N3. - С. 1-16.

22. Глушков В.М., Цейтлин Г.Е., Ющенко E.JI. Многоуровневое структурное проектирование программ: формализация метода - сфера приложений//Кибернетика. - 1981. - N4. - С. 42-66.

23. Гретцер Г. Общая теория решеток. - М.: Мир, 1982. -452 С.

24. Гросс М,, Лантен А. Теория формальных грамматик. - М.: Мир, 1971. - 294 с.

25. Ершов А.П. Современное состояние теории схем программ//Проблемы кибернетики. Выпуск 27, - 1974. - С. 87-111.

26. Ершов А.П. Введение в теоретическое программирование. -М.: Наука, 1977. - 288 с.

27. Иванов П.М. Автоматные выражения в системе алгоритмических алгебр с коммутативной алгеброй условий//Кибернетика. - 1978. - N2. - С. 16-20.

28. Капитонова Ю.В, Дискретные системы и задачи их реализации//Кибернетика, - 1975. - N4, - С, 7-11; № 5. - С. 21-27.

29. Капитонова Ю.В. Проблемы проектирования прикладных программных систем//Механизация и автоматизация управления. -1991. - № 5. - С. 4-12.

30. Капитонова Ю.В., Летичевский A.A. Математическая теория проектирования вычислительных систем. - М.: Наука, 1988. - 296 с.

31. Капитонова Ю.В., Летичевский A.A. Методы и средства алгебраического программирования. //Кибернетика и системный анализ. - 1993. - N3. - С. 7-12.

32. Капитонова Ю.В,, Летичевский A.A. О конструктивных математических описаниях предметных областей//Кибернетика. - 1988. - N4. - С. 17-25.

33. Кекелия В.И., Кирсанов Г.М., Цейтлин Г.Е. Реализация средств алгоритмических алгебр в однородных

структурах//Кибернетика. - 1974. - N5. - С. 29-36.

34. Кемени Дж., Снелл Дж, Конечные цепи Маркова. - М.; Наука, 1970. - 271 с.

35. Кирсанов P.M., Цейтлин Г.Е. Некоторые вопросы полноты аксиоматической системы в алгоритмических алгебрах//Кибернетика. -1977. - N4. - С. 35-37.

36. Кожевникова Г.П. Структуры данных и проектирование эффективной вычислительной среды. - Львов: Вища школа, 1986. -175 с.

37. Кокорева Л.В., Перевозчикова О.Л., Ющенко Е.Л. Диалоговые системы и представление знаний, - Киев: Наукова думка, 1993. -448 с.

38. Кон П. Универсальная алгебра. - М.: Мир, 1968. - 351 с.

39. Котов В.Е. Сети Петри. - М.: Наука, 1984. - 160 с.

40. Котов В.Е., Сабельфельд В.К. Теория схем программ. - М. : Наука, 1991. - 248 с.

41. Криницкий H.A. Аналитическая теория алгоритмов. - М.: Наука, 1994. - 351 с.

42. Лаллеман Ж. Полугруппы и комбинаторные приложения. - М.: МИр, 1985. - 440 с.

43. Летичевский A.A. Функциональная эквивалентность дискретных преобразователей. Ч. 1-3//Кибернетика. - 1969. - N2. -С. 15-17/ 1970. - N2. - С. 14-21/ 1972. - N1. - С. 1-5.

44. Летичевский A.A. Эквивалентность автоматов с заключительным состоянием. Ч.1-2.//Кибернетика, 1966. - № 4. -С. 14-18/ 1967. - № 1. - С. 6-12.

45. Летичевский A.A. Эквивалентность автоматов с заключительным состоянием относительно свободной полугруппы с правым нулем.//ДАН СССР, 1968. - 182; - № 5. - С. 8-10.

46. Летичевский A.A., Горлач С.П. Многоосновная алгебра структур данных//Математическое обеспечение систем логического вывода и дедуктивных построений на ЭВМ. - Киев: Ин-т кибернетики им. В.М.Глушкова АН УССР, 1983. - С. 18-31.

47. Лисовик Л.П. Проблема включения и эквивалентности для схем программ и формальных языков// Кибернетика и системный анализ. - 1993. - №2. - С. 62-73.

48. Мальцев А.И. Алгебраические системы. - М.: Наука, 1970. -391 с.

49. Мальцев А.И. Алгоритмы и рекурсивные функции. - М.: Наука, 1986. - 368 с.

50. Общая алгебра. Т.1. - М.: Наука, 1990. - 592 с.

51. Общая алгебра. Т.2. - М..< Наука, 1991, - 480 с.

52. Одинцов В.Е., Романов А.Н., Суржко C.B. О некоторых подходах к организации информационных фондов АСУ на основе интеграции баз данных//Машинная обработка экономической информации на ЭВМ. Сборник научных трудов. - М.: МЭСИ, 1980. - С. 31-39.

53. Одинцов Б.Е., Романов А.Н., Суржко C.B. О некоторых методах определения состава интегрированного фонда АСУ //Современные проблемы обработки экономической информации в АСУ. Сборник научных трудов. - М.: МЭСИ, 1981. - С. 39-49.

54. Одинцов Б.Е., Суржко C.B. Метод определения уровня дублирования данных в информационном фонде АСУ//Теория и практика проектирования информационного обеспечения АСУ. Сборник научных трудов. - М.: МЭСИ, 1981. - С. 50-63.

55. Пакет прикладных программ "Декомпозиция информационной базы", инв. № 1030//Отраслевой фонд алгоритмов и программ (ОФАП АСУ Минприбора). Каталог. - Калинин:'Центрпрограммсистем, 1983. -313 с.

56. Панфиленко В.П. Согласованность формализованных спецификаций при многоуровневом проектировании программ // Кибернетика и системный анализ. - 1993, - № 2. - С. 73-85.

57. Перевозчикова О. Л., Ющенко Е.Л. Диалоговые системы, -Киев: Наукова думка, 1990. - 184 с,

58. Редько В.Н. Основания композиционного программирования//Кибернетика. - 1979. - N3. - С. 3-19.

59. Редько В.Н., Ющенко Е.Л. Алгоритмические языки и транслирующие системы//Кибернетика. - 1967, - N5. - с. 87-^91.

60. Рейуорд-Смит В.Дж, Теория формальных языков. Вводный курс. - М.: Радио и связь, 1988. - 128 с.

61. Романов А.Н., Одинцов Б.Е., Суржко C.B. О задаче структуризации интегрированного информационного фонда для обслуживания пользователей различного типа//Применение методов вычислительной математики в экономике. Сборник научных трудов. -М.: МЭСИ, 1981. - С. 31-44,

62. Романов А.Н., Одинцов Б.Е., Суржко C.B. Структуризация информационных фондов систем управления//Технология реализации многоуровневых систем управления базами данных. Сборник научных трудов. - М.: МЭСИ, 1982. - С. 28-41.

63. Романов А.Н., Суржко C.B. Генераторы дискретных процессов: модели и приложения // Первый Всемирный Конгресс Общества математической статистики и теории вероятностей им. Бернулли: Тезисы докладов. - М.: Наука, 1986. - С. 993.

64. Романов А.H., Суржко C.B. Основы автоматизации

проектирования информационно-управляющих систем. - М.: МЭСИ, 1985.

/

- 107 с.

65. Романов А.Н., Суржко C.B. Теоретические основы построения сложных экономических систем. - М.: МЭСИ, 1981. - 88 с.

66. Романов А.Н., Суржко C.B., Одинцов Б.Е. Оптимизационная модель определения состава баз данных для запросных задач //Исследование проблем проектирования информационного и программного обеспечения АСУ. Сборник научных трудов. - М.: МЭСИ, 1981. - С. 39-49.

67. Саломаа А. Жемчужины теории формальных языковт — М. : Мир, 1986. - 159 с.

68. Семенов A.JI. Логические теории одноместных функций на натуральном ряде//Известия АН СССР. Серия математическая. - 1983.

- Т. 43. - № 3; - С. 623-658.

69. Сикорский Р. Булевы алгебры. - М.: Мир, 1969. - 375 с.

70. Стогний А.А., Гринченко Т.А. ЭВМ МИР и пути развития машинного интеллекта//Кибернетика. - 1987. - N6. - С. 72-80.

71. Суржко C.B. Алгебра О-регулярних елемент1в та ii властивост!//Всеукра!нська наукова конференция "Застосування обчислювально! техн1ки, математичного моделювання та математичних метод!в у наукових досл!дженнях. Тези допов!дей. - Льв1в, 1995. -С. 85.

Суржко C.B. Алгебры К-регулярных схем и алгоритмические алгебры//Друга укра!нська конференц1я з автоматичного керування "Автоматика-95". Прац1. Том 2. - Льв1в, 1995. - С. 137.

73. Суржко C.B. Генераторы дискретных процессов//Седьмая Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов и сообщений. Часть 1; - Львов, 1989. - С. 224-225.

74. Суржко C.B. Моделирование, анализ и компьютеризация информационных процессов на основе математической модели системы управления//Компьютеризация информационных процессов в управлении народным хозяйством. Тезисы докладов Всесоюзной научной конференции. Часть 2. - М.: МЭСИ, 1988. - С. 84-85.

75. Суржко C.B. Некоторые свойства сопряженных нагруженных графов//Вестник Львовского университета. Серия экономическая. Выпуск 18. - Львов: Вища школа, 1986. - С. 79-80.

76. Суржко С.В, Об одном подходе к описанию многоуровневых схем алгоритмов//Пятая Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов и сообщений. Часть 2. -Львов, 1985. - С. 91.

77. Суржко C.B. Об S-алгебрах и их обобщениях//Восьмой Всесоюзный семинар "Параллельное программирование и высокопроизводительные структуры". Тезисы докладов. - Киев ; Ин-т кибернетики им. В.М.Гдушкова АН УССР, 1988. - С. 7-8.

78. Суржко C.B. О вычислении значений операторов, заданных регулярными схемами//Кибернетика. - 1989. - N6. - С. 75-77,82.

79. Суржко C.B. О двух подходах к формализованному описанию и исследованию систем управления //Методы синтеза и планирования развития структур крупномасштабных систем. Тезисы докладов У Всесоюзного семинара. - М.: Ин-т проблем управления, 1990. -

С. 15.

80. Суржко C.B. О динамических сетевых моделях информационно-управляющих систем//Распределенные информационно-управляющие

системы. - Саратов: Изд-во Саратовского университета, 1988. -С. 21.

81. Суржко C.B. О категорном подходе к изучению алгоритмических алгебр//Кибернетика и системный анализ. - 1993. -N2. - С. 50-62.

82. Суржко C.B. О моделировании действий и ситуаций в экспертных системах//Восьмой Всесоюзный семинар "Параллельное программирование и высокопроизводительные структуры". Тезисы докладов. - Киев: Ин-т кибернетики им. В.М.Глушкова АН УССР, 1988. - С. 199.

83. Суржко C.B. О некоторых классах алгоритмических алгебр//Кибернетика. - 1990. - N2. - C.I08-II2.

84. Суржко C.B. О полугрупповых свойствах параллельных процессов//X Всесоюзный семинар "Параллельное программирование и высокопроизводительные системы: методы представления знаний в информационных технологиях". Тезисы докладов, - Киев: Ин-т кибернетики им. В.М.Глушкова АН УССР, 1990. - С. 7.

85. Суржко C.B. Об управляемых динамических системах//Теоретико-системные методы и их использование в автоматизированных системах. - Киев: Ин-т Кибернетики АН УССР, 1983. - С. 36-40.

86. Суржко C.B. О сетевых моделях дискретных преобразователей информации//Кибернетика и системный анализ. - 1991. - N5. -

С.83-90.

87. Суржко C.B. О языках, порождаемых дискретными преобразователями//Цифровые устройства и микропроцессоры в системах передачи информации. Межвузовский сборник научных трудов ХИИТ. - Харьков: ХИИТ, 1987. - С. 58-62.

88. Суржко C.B. Организация вычислений в соответствии с регулярными схемами операторов//Седьмая Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов и сообщений. Часть 1. - Львов, 1989. - С. 226.

89. Суржко C.B. Полугруппы дискретных процессов и минимизация бесконечных автоматов//Шестая Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов.

Часть 3. - Львов, 1987. - С. 20-21.

•90. Суржко C.B. Полугруппы и структурирование автоматов //XIX Всесоюзная алгебраическая конференция. Тезисы сообщений. Часть 1.

- Львов, 1987. - С. 270.

91. Суржко C.B. Расширения системы алгоритмических алгебр//Шестая Всесоюзная школа-семинар "Распараллеливание обработки информации". Тезисы докладов. Часть 1. - Львов, 1987. -С. 77-78.

92. Суржко C.B. Совершенствование информационного обеспечения

- основа повышения качества функционирования интегрированной системы управления//Средства связи. Выпуск 1. - М.: ЦООНТИ "ЭКОС", 1989. - С. 10-12.

93. Суржко C.B. Структурирование и декомпозиция дискретных преобразователей//Декомпозиционные методы проектирования систем. -Киев: Ин-т кибернетики им. В.М.Глушкова АН УССР, 1988. - С. 49-55.

94. Суржко С»В. Схемы функционирования дискретных систем управления//Синтез структур автоматизированного управления в крупномасштабных системах. Тезисы докладов Всесоюзного семинара. -Херсон, 1989. - С. 7-8.

95. Суржко C.B. Фильтрация дискретных процессов//Проблемы бионики. Выпуск 41. - Харьков: Вища школа, 1988, - С. 109-113,

96. Суржко C.B., Кример A.A. Моделирование и программные средства синтеза и анализа системы управления предприятием//Управляющие системы и Машины. - 1990. - №5. -С. 107-112.

97. Суржко C.B., Плаксин В.Ф., Сыпа И.М. Модельный подход к анализу, разработке и сопровождению интегрированной автоматизированной системы управления//Практическое применение современных технологий программирования, пакетов прикладных программ в вычислительных системах и сетях ЭВМ. Тезисы докладов 1 Всесоюзной научно-технической конференции. - Днепропетровск, 1988. - С. 150-151.

98. Суржко C.B., Ющенко Е.Л. О языках над алфавитом, интерпретированным в булевой алгебре //Друга украд.нська конференц1я з автоматичного керування "Автоматика-95". Прац1. Том 2. - JlbBiB, 1995. - С. 137-138.

99. Суржко C.B., Ющенко E.JI. О языках над алфавитом, интерпретированным в булевой алгебре// Кибернетика и системный анализ. - 1995. - №3. - С. 86-106.

100. Суржко C.B. О функциях от элементов упорядоченного пространства/ /Вестник Львовского университета. Серия экономическая. Выпуск 15. - Львов: Вища школа, 1983. - С. 73-75.

101. Тыугу Э.Х. Концептуальное программирование. - М. : Наука, 1984. - 340 с.

102. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. - М.: Наука, 1987. - 288 с.

103. Фукс Л. Частично упорядоченные алгебраические системы. -М. : Мир, 1965. - 342 с.

104. Хоар Ч. Взаимодействующие последовательные процессы. -М.: Мир, 1989. - 264 с.

105. Цейтлин Г.Е. Алгоритмические алгебры структур данных и многоуровневое проектирование программ//Программирование. - 1986. - № 3. - С. 3-16.

106. Цейтлин Г.Е. Кокструирование алгоритмов символьной обработки// Кибернетика и системный анализ. - 1993. - № 2. -С. 17-30.

107. Цейтлин Г.Е. Проблема тождественных преобразований схем структурированных программ с замкнутыми логическими условиями,

Ч. 1-3//Кибернетика. - 1978. - N3. - С. 50-57; N4. - C.I0-I8; 1979. - N5. - С. 44-51.

108. Цейтлин Г.Е., Ющенко Е.Л. Многоуровневое структурное представление знаний (анализ, трансформация, синтез)//1У Всесоюзная конференция "Применение методов в математической логике". Тезисы докладов. - Таллин, 1986. - С. 183-185.

109. Цейтлин Г.Е., Ющенко Е.Л. Теоретические и прикладные аспекты структурного многоуровневого программирования //Кибернетика. - 1987. - N5. - С. 38-48.

110. Цейтлин Г.Е., Ющенко Е.Л. Формализованные спецификации и трансформационный синтез программ// Кибернетика и системный анализ. - 1993. - № 1. - С. 127-153.

111. Юдицкий С.А., Магергут В.З. Логическое управление дискретными процессами, - М.: Машиностроение, 1987. - 175 с.

112. Ющенко Е.Л., Цейтлин Г.Е, Многоуровневый синтез структурированных программ//Кибернетика, - 1982. - N5. - С. 11-21.

113. Ющенко E.JI., Цейтлин Г.Е., Грицай В.П., Терзян Т.К. Многоуровневое структурное проектирование программ: теоретические основы, инструментарий. - М.: Финансы и статистика, 1989. - 208 с.

114. Ющенко E.JI., Цейтлин Г.Е., Суржко С.В. Алгоритмические алгебры Глущкова и проблемы моделирования систем //Кибернетика и системный анализ. - 1993.' - N3. - С. 106-116.

115. Ющенко Ю.А. Тождественные преобразования в алгебрах недетерминированных алгоритмов. Ч.1,2//Кибернетика. - 1985. — №6. - С. 9-15/ 1986. ~ №6. - С. 31-36.

116. Языки и автоматы. - М.: Мир, 1975. - 358 с.

117. Aalbersberg I.J., Rozenberg G. Theory of traces // Theoretical Computer Science. - 1988. - 60. - P. 1-82.

118. Berry G., Sethi R. From regular expressions to deterministic automata// Theoretical Computer Science. - 1986, -48. - P. 117-126.

119. Czaja L. A calculus of nets// Кибернетика и системный анализ. - 1993. - №2. - С. 40-50.

120. Duboc Ch. Mixed product and asynchronous automata // Theoretical Computer Science. - 1986. - 48. - P. 183-199.

121^ Feather M.S. A survey and classification of some program transformation approaches and techniques//Program Specification and Transformation. - Amsterdam: North-Holland, 1987. -P. 165-195.

122. Hoar C.A.R. Mathematics of programming//BYTE. - 1986. -August. - P. 17-25.

123. Mazurkiewicz A. Traces, histories, graphs: instances of a process monoid//Lecture Notes in Computer Science. - 1984. -176. - p. 115-133.

124. Mazurkiewicz A. Semantics of concurrent systems: a modular fixed point trace approach//Lecture Notes in Computer Science. - 1985. - 188. - P. 353-375'.

125. Ochmanski E. Regular behaviour of concurrent systems // Bull. EATCS, 1985, 27, Oct. - P.56-67.

126. Sakarovitch J. On regular trace languages// Theoretical Computer Science. - 1987. - 52. - P. 59-75.

127. Shoemaker S. Simulation today//Computer Networks and Simulation III. - Amsterdam: Elsevier Publishers, 1986. -

P. 27-39.

128. Winkowski J. An algebra of processes//Journal of Computer and System Sciences. - 1987. - 35. - P. 206-228.