ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ

управ ляющих систем - преобразования, сохраняющие отношение эквивалентности (о. э.) управляющих систем (у. с.). Используются в задачах оптимизации, контроля, а также как средство характеризации (напр., аксиоматизации) определенных классов у. с.; вывод в формальных системах также можно рассматривать как Э. п. управляющих систем. В качестве о. э. обычно рассматривают функциональную эквивалентность, т. е. в этом случае эквивалентными являются у. с., имеющие одинаковые функции. Иногда по тем или иным соображениям рассматривают и другие о. э .
С Э . п. <управляющих систем связан широким круг задач, конкретная постановка к-рых варьируется в зависимости от особенностей рассматриваемого класса у. с. Основные из этих задач следующие.
1. Построение конечных (или рекурсивных) полных систем правил преобразований. Система правил Э. п. наз. полной для данного класса у. с., если с помощью конечного числа применений этих правил произвольную у. с. из рассматриваемого класса можно преобразовать в любую эквивалентную ей у. с. Решение этой задачи существенно зависит как от класса у. с. и о. э. в нем, так и от допустимых средств преобразований.
Наиболее распространены такие постановки задачи, когда средства решения ограничиваются следующим образом. Определяют понятие фрагмента (или подсхемы) у. с. и рассматривают преобразования у. с., состоящие в замене одних фрагментов у. с. другими. Таким образом, пара фрагментов определяет множество преобразований произвольной у. с. каждое из к-рых состоит в замене нек-рого вхождения фрагмента в фрагментом (если не содержит вхождений фрагмента то считается, что преобразование, определяемое парой оставляет без изменения). Пара фрагментов наз. правилом для данного класса у. с., если преобразования, определяемые этой парой, сохраняют о. э., то есть переводят произвольную у. с. из данного класса в эквивалентную ей. Нек-рые правила могут быть снабжены условиями их применимости, описывающими ситуации, в к-рых их разрешается применять, и гарантирующими сохранение о. э. Если правило применимо к любому вхождению фрагмента во всякой у. с., то оно наз. локальным. Нелокальность правила обычно означает, что его применимость определяется строением всей у. с. Понятие полноты системы правил часто определяют в следующей форме.
Говорят, что пара фрагментов выводима из системы правил если фрагмент с помощью правил из можно преобразовать во фрагмент (применение правил к фрагменту определяется так же, как и для у. с.). Система правил наз. полной, если из нее выводимы все пары вида где и - эквивалентные у. с. Обычно наряду с правилами рассматриваются схемы правил, содержащие те или иные параметры (свободные переменные). Каждая схема правил путем придания параметрам конкретных значений порождает в общем случае бесконечное множество правил, и наиболее распространенная постановка задачи состоит в том, чтобы для данного класса у. с. найти конечную полную систему схем правил.
2. Проблема полноты систем правил преобразований (как для индивидуальных систем, так и в алгоритмич. плане): по системе правил определить, является ли она полной или нет.
3. Построение эффективных процедур, порождающих о. э. Эта задача является ослаблением первой. В качестве средств решения допускаются произвольные алгоритмы, а также недетерминированные формально описанные процедуры.
4. Построение оптимизирующих (или вообще целенаправленных) процедур преобразований. Наиболее часто речь здесь идет о минимизации сложности схем у. с. либо о преобразовании у. с. в нек-рую канонич. форму, единственную в классе эквивалентности. В последнем случае решение задачи дает и разрешающую процедуру для о. э. Целью преобразовании может быть также построение самокорректирующихся или других специальных у. с. С задачей оптимизации связан целый ряд задач метрическою характера, например получение оценок сложности решений, доли оптимальных у. с. и т. п.
5.Проблема разрешения для задач первого типа, т. е. вопрос о существовании конечной или рекурсивной полной системы правил преобразований для произвольного класса у. с. из нек-рого бесконечного множества классов. Таким множеством классов у. с. может быть, напр., совокупность множеств всех термов однотипных алгебр или совокупность классов схем из функционалъных элементов в различных базисах н т. п.
Особенности конкретных классов у. с. накладывают отпечаток на постановку и методы решения указанных задач. Ниже рассмотрены нек-рые примеры.
Э. <п. в алгебрах. Каждой алгебре нек-рой сигнатуры соответствует бесконечный класс у. с.- множество всех термов (формул) данной сигнатуры (вместе с определяемыми ими функциями). Естественным о. э. на множестве термов является отношение функциональной эквивалентности: термы t₁ и t₂ эквивалентны тогда и только тогда, когда они определяют одну и ту же функцию с точностью до несущественных аргументов. В этом случае обычно пишут: t₁=t₂ (или и такие выражения наз. тождествами или равенствами данной алгебры. В качестве фрагментов термов рассматриваются подтермы, т. е. такие части, к-рые сами являются термами. Так как любая замена подтерма эквивалентным ему термом сохраняет о. э., то любое тождество алгебры (рассматриваемое как неупорядоченная пара термов) является локальным правилом. Всякое тождество алгебры можно рассматривать и как схему правил, параметрами к-рой являются переменные. Поэтому для алгебр задача 1 приобретает следующий вид: для данной алгебры найти конечную полную систему тождеств, рассматриваемых как схемы правил, т. е. в этом случае задача 1 Э. п. совпадает с задачей алгебраич. аксиоматизации алгебр.
Существование конечной полной системы тождеств является функциональным свойством алгебр, т. е. оно полностью определяется классом функций, выразимых в данной алгебре, и не зависит от сигнатуры. Любая функционально полная (конечная) алгебра имеет конечную полную систему тождеств; любая двухэлементная алгебра имеет конечную полную систему тождеств; существуют трехэлементные группоиды, конечные полугруппы и бесконечные группы, не имеющие конечных полных систем тождеств; любая конечная группа имеет конечную полную систему тождеств; для алгебр всех рекурсивных функций, а также для алгебры регулярных событий задача 1 решается отрицательно.
Э. п. схем из функциональных элементов. Понятие схемы из функциональных элементов (с. из ф. э.) можно рассматривать как обобщение понятия терма. Класс с. из ф. э. в нек-ром базисе реализует то же множество функций, что и алгебра с набором сигнатурных операций, соответствующим данному базису. Поэтому результаты, относящиеся к задаче Э. п. для алгебр, переносятся с небольшими модификациями на с. из ф. э. Фрагментами с. из ф. э. являются подсхемы, отличающиеся от с. из ф. э., быть может, только наличием нескольких выходов.
Э. н. контактных схем. Как и для термов, понятие фрагмента совпадает с понятием контактной схемы (к. с.). Требует уточнения только определение множества полюсов во вхождении фрагмента в схему. Две к. с., между полюсами к-рых установлено взаимно однозначное соответствие, считаются эквивалентными, если функция проводимости между произвольными полюсами одной схемы совпадает с функцией проводимости между соответствующими полюсами другой. Если пары эквивалентных к. с. рассматривать как схемы правил, параметрами к-рых являются буквы, приписанные ребрам схем, и считать, что каждая такая схема порождает правила только путем переименования этих букв, то для класса всех к. с. не существует конечной полной системы схем правил. В то же время для любого пдля класса всех к. с., ребрам к-рых приписано не более празличных букв, конечная полная система таких схем правил существует. Если же допустить порождение конкретных правил из схем путем согласованной замены ребер с одинаковыми буквами произвольными к. с., то и для класса всех к. с. может быть построена конечная полная система правил.
Э. п. автоматов. Для автоматов конечных не существует конечной полной системы локальных правил преобразований. Однако с использованием нелокальных правил или схем правил, зависящих от специальных параметров, задача 1 для них может иметь положительное решение. С конечными автоматами связана алгебра регулярных событий, элементами к-рой являются множества слов, представимые (распознаваемые) конечными автоматами, а сигнатурными операциями служат объединение конкатенация ху и итерация х*. Для этой алгебры не существует конечной полной системы тождеств. Однако подалгебра, состоящая из всех событий, содержащих пустое слово, имеет конечную полную систему тождеств.
Э. п. алгоритмов. Для полного класса алгоритмов и функционального отношения эквивалентности проблема Э. п. имеет отрицательное решение, поскольку отношение функциональной эквивалентности в этом случае не является рекурсивно перечислимым. Поэтому для получения положительных решений либо сужают класс алгоритмов, либо прибегают к модификации постановки проблемы. Для задания подклассов алгоритмов часто используют конечные автоматы, автоматы с магазинной или стэковой памятью, дискретные преобразователи различного ьида, программы с ограничениями на топологическую структуру или на объем рабочей памяти и т. п. Иногда подклассы алгоритмов выделяются по функциональному признаку путем задания класса вычислимых функций. В последнем случае обычно задается определенное базисное множество функций, к-рое замыкается с помощью таких операций, как суперпозиция, рекурсия, ограниченное суммирование и т. п. Однако для выделяемых таким путем классов алгоритмов отношение функциональной эквивалентности оказывается разрешимым лишь в тех случаях, когда соответствующий класс функций достаточно беден.
Поэтому развиваются другие подходы, в частности подход, основанный на изучении схем алгоритмов. Схемы алгоритмов отличаются от алгоритмов в основном способом приписывания им функций. При этом отношение эквивалентности схем алгоритмов рассматривается как определенная аппроксимация отношения функциональной эквивалентности алгоритмов, так что решение проблемы Э. п. для схем алгоритмов можно считать приближенным решением этой проблемы для алгоритмов. Однако и здесь положительные решения удается получать лишь для достаточно грубых приближений, близких к конечным автоматам. Возможность получения положительных решений для класса всех алгоритмов появляется при ослаблении понятия полноты системы правил, напр. при отказе от требования конечного числа применений правил. Точное, система правил наз. предельно полной, если, применяя ее правила, можно любые два эквивалентных алгоритма преобразовать в пределе, т. е. за бесконечное число шагов, в один (в общем случае бесконечный) вычислительный комплекс. Конечную предельно полную систему схем локальных правил оказалось возможным построить для функционально полного класса всюду определенных программ в нек-ром простом базисе. Реальный смысл предельной полноты состоит, в частности, в том, что предельно полные системы являются полными в обычном смысле для класса программ, вычисляющих конечные функции.
В связи с задачей оптимизации у. с. важную роль играют направленные преобразования, дающие в конечном с/чете оптимальные или близкие к ним у. с. В частности, большой интерес представляет изучение возможностей монотонных преобразований, к-рые на каждом шаге не повышают сложность у. с. в том или ином смысле.

Лит.: [1] Янов Ю. И., лMitt. Math. Ges. DDK