ПРОГРАММИРОВАНИЕ, 2011, No 6, с. 33-43
- ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ПРОГРАММИРОВАНИЯ -
УДК 681.3.06
ОБ ОДНОЙ МЕТОДИКЕ РАСПОЗНАВАНИЯ ЭКВИВАЛЕНТНОСТИ В АЛГЕБРАИЧЕСКИХ МОДЕЛЯХ
ПРОГРАММ
© 2011 г. Р.И. Подловченко НИВЦ МГУ 119991 Москва, Ленинские горы, дом 1, стр. 4 E-mail: rip@vvv.srcc.msu.ru Поступила в редакцию 23.05.2011 г.
В статье изучается задача проверки эквивалентности схем программ в уравновешенных полугрупповых моделях программ. Для этой задачи предложен метод построения разрешающих алгоритмов в том случае, если полугрупповая модель программ обладает свойством левого сокращения h^h^ = h\h3 ^ h = h3. Показано также, что проверку эквивалентности схем программ можно осуществить за время, полиномиально зависящее от размеров проверяемых схем, если уравновешенная полугрупповая модель программ наряду со свойством левого сокращения обладает также и свойством правого сокращения h^hi = НзН\ ^ Н = Нз.
1. ВВЕДЕНИЕ
Рассматриваемые в статье алгебраические модели программ введены в [1] и представляют собой математические модели вычислений, объектами которых являются схемы программ. Каждая алгебраическая модель программ строится над выбранным конечным базисом операторных символов и логических переменных, заменившими собой в моделируемых программах операторы и логические условия.
При фиксированном базисе все алгебраические модели имеют общее множество своих объектов, и одна отличается от другой отношением эквивалентности объектов. Проблема эквивалентности в отдельной модели состоит в поиске алгоритма, который, получив на свой вход две схемы программ из этой модели, распознаёт, эквивалентны они в ней или нет. Если такой алгоритм найден, то он именуется разрешающим эквивалентность в этой модели.
В теории алгебраических моделей программ установлено существование моделей с неразрешимой проблемой эквивалентности, т.е. таких, для которых нет разрешающих
в них эквивалентность алгоритмов. Это обстоятельство и выдвигает задачу разработки методик распознавания эквивалентности в алгебраических моделях программ.
Здесь уместно отметить следующее. Алгебраическими моделями программ описываются такие модели, как дискретные преобразователи, введённые в [2], а именно: для каждого дискретного преобразователя можно построить равносильную ему схему программы. На этом основании факты по разрешению эквивалентности дискретных преобразователей переносятся в теорию алгебраических моделей программ. В частности, переносится предложенная в [3] методика распознавания эквивалентности дискретных преобразователей. Однако её применение приводит к разрешающим алгоритмам, имеющим экспоненциальную сложность относительно размеров сравниваемых объектов. Такие алгоритмы неприемлемы на практике.
Актуальность приобретает задача разработки такой методики, которая ведёт к построению разрешающих эквивалентность алгоритмов приемлемой сложности; таковой можно считать полиномиальную сложность. Излагаемая в
статье методика удовлетворяет этому требованию. Результаты её применения опубликованы в [4, 5].
Наша методика по замыслу восходит к хорошо известной методике распознавания эквивалентности конечных автоматов-ацеп-торов, т.е. принимающих регулярные языки. В обеих методиках предусматриваются два этапа исследований. На первом устанавливается факт разрешимости эквивалентности, что осуществляется построением алгоритмов экспоненциальной сложности. На втором этапе конструируются разрешающие алгоритмы полиномиальной сложности относительно размеров сравниваемых объектов модели.
Материал статьи распределён по пяти разделам. В первом разделе описываются матричные схемы программ, для которых и рассматривается проблема эквивалентности. Обоснованием этому служит факт, установленный в [4]: проблема эквивалентности в любой алгебраической модели программ сводится к проблеме эквивалентности в множестве матричных схем, принадлежащих модели; при этом сводящий алгоритм является полиномиальным по сложности относительно размеров схем. Во втором разделе формулируются задачи первого этапа исследований, предписываемых нашей методикой; это задачи а и в. Их решение для модели программ гарантирует решение в ней проблемы эквивалентности (теорема 1). Здесь же даётся решение задачи а для так называемых уравновешенных моделей программ (теорема 2). В третьем разделе ставится задача 7 и выявляется множество алгебраических моделей программ, для которых решение задачи 7 является достаточным условием решения задачи в; это уравновешенные полугрупповые модели программ с левым сокращением (теорема 3). Четвертый раздел посвящён доказательству того, что для выявленных моделей задача 7 имеет решение. Этим завершается первый этап исследований. В пятом разделе излагается второй этап. Устанавливается, что среди выявленных моделей имеется семейство таких, для которых можно предложить алгоритмы, разрешающие эквивалентность схем с полиномиальной
сложностью относительно размеров схем (теорема 5). Отмечаем, что к выявленным моделям относятся так называемые коммутативные модели программ, рассмотренные в [6]; для них сложность распознавания эквивалентности схем программ оценивается величиной O(n2 log n), где n - размер схем.
В заключение заметим, что в [7, 8] предлагается другая методика распознавания эквивалентности в моделях программ, тоже нацеленная на построение приемлемых по сложности распознающих алгоритмов. Сравнение результатов применения этой методики и методики, изложенной в данной статье, - дело будущего.
2. ОСНОВНЫЕ ПОНЯТИЯ
Введём понятие матричной схемы программ, принадлежащей любой алгебраической модели программ. Пусть последняя строится над конечными алфавитами Y, P; элементы множества Y называются операторными символами, а элементы множества P -логическими переменными.
Синтаксически матричная схема над Y, P представляет собой конечный ориентированный и размеченный граф, вершины которого подразделяются на вход схемы, выход схемы, пустой цикл и преобразователи; при этом вход, выход и пустой цикл присутствуют обязательно. Из любой вершины, кроме выхода и пустого цикла, исходят дуги в количестве, равном числу элементов в множестве X, где X = {x | x : P ^ {0,1}}. Каждая дуга помечена элементом из X, причём различные дуги несут различные метки. Вход схемы не имеет оканчивающихся в нём дуг. Каждый преобразователь в схеме несёт в качестве метки символ из Y. Этим структура матричной схемы описана.
Далее элементы множества X именуются наборами значений логических переменных из P или кратко: наборами; вершина, в которую из вершины v схемы ведёт дуга с меткой x, называется x-преемником вершины v.
Семантически каждая матричная схема над Y, P является носителем отображения, в общем случае - частичного, множества L, состоящего из всех функций разметки над Y, P,
в множество У*, состоящее из всех слов над алфавитом У. Здесь функцией разметки над У, Р называется всюду определённое отображение множества У* в множество X. Далее элементы множества У * называются операторными цепочками. Реализуемое матричной схемой отображение осуществляется посредством процедуры её выполнения на функциях разметки. Пусть ц е £. Процедура выполнения схемы на ц представляет собой обход схемы, начинающийся в её входе, сопровождаемый построением операторной цепочки и подчиняющийся следующим правилам.
Пусть г>о - вход схемы. Тогда по функции ц определяется набор х, равный ц(Д), где А -пустая операторная цепочка, и выход из вершины го совершается по исходящей из неё дуге с меткой х.
Допустим, что при обходе достигнута вершина г схемы, и к - построенная к этому моменту операторная цепочка. Тогда, если г -преобразователь с меткой у, то цепочка к трансформируется в цепочку ку, находится набор ц(ку), и выход из вершины г совершается по дуге, помеченной этим набором.
Если г - выход схемы или пустой цикл, то обход схемы прекращается. В первом случае говорится, что схема остановилась на функции ц с результатом к. Во втором случае выполнение схемы на ц считается безрезультатным.
Так определяется отображение схемой множества С в множество У *.
Как было отмечено во введении, отдельная алгебраическая модель программ определяется введением отношения эквивалентности между схемами программ. Каждое отношение эквивалентности схем индуцируется двумя параметрами:
- отношением эквивалентности V в множестве У*;
- подмножеством Ь множества С.
Опишем его для матричных схем. Матричные схемы С1,С2, по определению, ^,Ь)-эквивалентны тогда и только тогда, когда, какой бы ни была функция ц из Ь, всякий раз, как одна из схем С\,С2 останавливается на ц,
останавливается и другая, и результатами их выполнения на ц являются v-эквивалентные операторные цепочки.
Алгебраическая модель программ с (V, Ь)-эквивалентностью схем программ обозначается М(V, Ь).
3. ЗАДАЧИ ПЕРВОГО ЭТАПА ИССЛЕДОВАНИЙ И РЕШЕНИЕ ОДНОЙ ИЗ НИХ
По аналогии со случаем конечных автоматов-ацепторов на первом этапе исследований, предписываемых методикой распознавания эквивалентности, выставляются две задачи; обозначим их а и в.
а. Для любого натурального числа N ввести алгоритмически проверяемое отношение N-эквивалентности матричных схем из модели М(V, Ь), проделав это таким образом, чтобы из их эквивалентности в М(V, Ь) всегда следовала их ^эквивалентность.
в. Для любой пары матричных схем из
модели М(V, Ь) алгоритмически определить число N(С\, С2) такое, чтобы из N(С1,С2)-эквивалентности схем С\,С2 вытекала их эквивалентность в модели М(V, Ь).
Очевидна теорема 1.
Теорема 1. Если для модели М (V,Ь) решены задачи а и в, то в ней разрешима эквивалентность матричных схем, следовательно, и схем произвольного вида.
Начнём с введения ^эквивалентности матричных схем из М (V,Ь). Определим необходимые для этого понятия.
Пусть ц — функция разметки из С, и N -натуральное число. N-префиксом функции ц называется функция, определённая на всех операторных цепочках из У*, имеющих длину N, и на каждой такой цепочке имеющая то же значение, что и функция ц.
Маршрутом в матричной схеме называется ориентированный путь в ней с началом во входе. Говорим, что маршрут в матричной схеме пролагается N-
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.