О пополнении группоида до программной алгебры

Программные алгебры GAPS (Generic algebraic program structure) были предложены Н. Н. Непейводой [1] в рамках развития алгебраических методов представления программных систем.

Задача вложения конечного группоида в конечную программную алгебру имеет прикладное значение для преобразования алгоритма в форму, пригодную для вычисления на алгебраическом процессоре. Она была поставлена и решена в работе [1] для полугрупп, затем было построено вложение группоида в бесконечную программную алгебру [2] .

В данной работе строится вложение конечного группоида в конечную программную алгебру, что завершает решение задачи.

Программная алгебра — бигруппоид с ассоциативной операцией «о» композиции программ и неассоциативной операцией «*» аппликации (применения программы к данным), которые связаны тождествами:

^(х * / ) * д = х * ( / ^о д ); 0 * х = х * 0 = 0;

х * е = х.

Проект проводится при финансовой поддержке государства в лице Минобрнауки России (идентификатор № RFMEFI61314X0030).

○c А. А. Демидов, 2015

○c Институт программных систем имени А. К. Айламазяна РАН , 2015

○c Программные системы: теория и приложения, 2015

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

С «переходной системой» ( Л, Q, p ) конечного автомата над входным алфавитом Л с множеством состояний Q и функцией переходов p : Q х Л ^ Q можно связать полугруппу подстановок на множестве Q [3 , 4] : каждой букве а Е Л на основе функции переходов поставим в соответствие подстановку

Р а : Q ^Q, p a ( q ) = p ( q,a )

перехода автомата из предыдущего состояния q в следующее. Последовательному действию букв а и b соответствует композиция

• (2)    Р аЬ = p b ( p a ( q )) = Р а ° P b .

Множество подстановок {p _a : а Е Л * } всех слов Л * в алфавите Л образует полугруппу Р д , называемую внутренней полугруппой автомата Л. Она изоморфна фактор-полугруппе полугруппы Л * с операцией конкатенации (соединения слов) по отношению

Я = { ( а,р ): а,Р Е Л * и Vq EQ ( p ( q, а ) = p ( q, ^ )) }.

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

Определение 1. Группоид G назовём редуктивным слева, если из того, что х • а = х • b для всех х Е G, следует а = b ( а,Ь Е G ) — см. [5] .

Лемма 1 (Основная). Каждый редуктивный слева конечный группоид допускает вложение во внутреннюю полугруппу конечного автомата.

Формула (2) устанавливает соответствие между выражениями вида а^Ь над элементами группоида G и композициями вида p _a о p , о p b над элементами полугруппы Р д . Для построения вложения G ^ Р д необходимо избавиться от подстановки p , , соответствующей символу операции.

Гомоморфизм, задаваемый левым сдвигом внутренней полугруппы Р д конечного автомата:

• (3)                      р х ^ р . х = р ^ ° р х

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

• (4)    ab О   р - ¹ о р , о р _а о р . о p _b = р - ¹ о р , _а о р . ь ,

где р ^-1 — формальная запись, определяющая тождество [р ^-1 о р, ] о р _а = р _а ; в общем случае элемента р ^-1 не существует, поскольку р , не обязательно является биекцией. Это не мешает нам с помощью некоторого символа # перевести конечный автомат в особое «начальное» состояние, когда последующий аргумент х на входе будет действовать как подстановка р _х , а не р , _х . Формально это означает вложение исходного группоида G в группоид G # с удвоенным множеством элементов.

Определение 2. Назовём элементы # х О р _х удвоенного группоида оригинальными, а элементы х О р , _х — сопряжёнными к ним.

Подстановка р#, соответствующая входному символу #, по построению — идемпотент: дважды перейдя в начальное состояние, окажемся там же. Руководствуясь выражением (4), формально можно записать:

2            -1

• р # = р # = р ^ ^о р ^ .

Конечный автомат тогда можно представить как функцию F : 2 < ^g # ) ^ Р д из множества наборов аргументов в множество подстановок, действующую следующим образом:

F (# a ) = р # о р а , F ( a ) = р ^ а , F ( b ) = р . ь , F (# ab ) = р # о р а о р , ь .

Пусть результат произведения ab в выражении (5) равен с. Формально выполним следующие преобразования:

F (# ab ) = р # о р а о р . ь = р^

• (6)         р . о F (# ab) = р . о р - ¹ о р ^ о р а о р ^ ь = р ^ о р _с ;

р ^ а о р ^ ь = р ^ с

— откуда следует, что подстановка р ^-1 в выражении (4) является левым сдвигом р ^ _х ^ р _х , возвращающим результат от сопряжённого к оригинальному виду.

Предложение 1. Если р , — биекция, то F — изоморфизм, определённый на сопряжённых элементах удвоенного группоида.

Доказательство. Так как язык А * распознаётся автоматом, и все оригинальные элементы удвоенного группоида различны, то на этих элементах функция F является однозначной. В силу биектив-ности р , левый сдвиг (3) является изоморфизмом, поэтому F будет однозначной и на сопряжённых элементах. Отсюда, с учётом выражений (5) и (6) , следует, что F — изоморфизм, определённый на сопряжённых элементах:

F ( а ) о F ( б ) = F ( ab ) .

Оригинальным элементам сопоставлены подстановки р _х , и они указанному изоморфизму, вообще говоря, не удовлетворяют. □

Предложение 2. Функция р , является биекцией тогда, когда G — редуктивный слева конечный группоид.

Доказательство. Пусть р , не является биекцией, то есть отображает некоторые элементы a = b в одну подстановку р , _a = р , ь . Тогда, согласно выражениям (5) , для любого элемента х будет верно:

F (# ха) = р # о р _х о р . a = р # о р _х о р . ь = F (# хЬ )

В силу регулярности языка А * если двум выражениям сопоставлена одна и та же подстановка, то эти выражения равны. Поэтому равенство F (# ха) = F (# xb) влечёт равенство х • а = х • b для всех х.                                                                     □

Замечание 1. Обратное неверно: подстановки р , _a = (221 2) , р , ь = (2 2 4 2) и р , _с = (2 2 2 2) дают контрпример х • a = х • b = с.

Доказательство основной леммы. Доказательство сводится к доказательству предложений 1 и 2.                            □

Формулировка леммы 1 ограничивает возможности метода. Пример 1 демонстрирует вложение конечного группоида в конечную программную алгебру, которое не может быть построено предложенным методом.

Пример 1. К полугруппе S с нулевым умножением ж • у = 0 для всех ж, у е S присоединим правую единицу: ж • е = ж, е • ж = 0. Полученный группоид G не является редуктивным слева. Определим на G программную алгебру с операциями аппликации ж * у = ж • у и композиции

ж о у =

!

при ж = е ;

иначе.

Группоид G вкладывается в эту алгебру по операции аппликации.

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

Предложение 3. Каждый конечный группоид допускает вложение в редуктивный слева конечный группоид.

Доказательство. Пусть группоид G содержит элементы а = Ь, такие что ж • а = ж • Ь для всех ж е G. Расширим его до группоида G ' , определив новый элемент е е G’ как единицу в G ' , так что е • ж = ж • е = ж для всех ж е G ' . Тогда е • а = а = Ь = е • Ь для любых а,Ь е G ' , таких что а = Ь. □

Теорема 1. Каждый конечный группоид допускает вложение в конечную программную алгебру.

Доказательство. В соответствии с леммой 1 и предложением 3 каждый конечный группоид вкладывается в конечную полугруппу. На элементах полугруппы Р д определим вторую операцию «*» так, чтобы соблюдались аксиомы программной алгебры (1) .

Так, можно взять фиксированный идемпотент d е Р д и положить ж * у = d о ж о у, тогда первая аксиома будет выполнена, поскольку

( ж * у ) * z = d о ( d о ж о у ) о z = d ² о ж о ( у о z ) = ж * ( у о z );

вторая аксиома выполняется при наличия нуля в Р д , поскольку

( ж * 0) * у = ж * (0 о у ) = ж * 0

^   0 о у = у о 0 = 0;

( ж * у ) * 0 = ж * ( у о 0) = ж * 0

третья аксиома выполняется при наличия правой единицы в Рд, поскольку

( ж * у ) * е = ж * ( у о е ) = ж * у ^ у о е = у.

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

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

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