Исследование некоторых задач в алгебрах и пространствах программ Казиев В.М.
    Рассмотрим пару алгебр (A,B): алгебру X= событий - алгоритмических процедур (программ) заданную над алфавитом X={x1,x2,...,xn} и В-трехзначную алгебру логики (0,1,2 - неопределенность). В алгебре А определим двухместные операции конъюнкции и условной дизъюнкции и одноместную операцию итерации следующим образом: конъюнкция s1?s2 событий s1, s2 состоит из всех слов вида pq, p? s1, q? s2; ? - дизъюнкция ?(s1+s2) совпадает с s1(s2), если условие ? истинно (ложно); итерация с постусловием {s}? состоит из пустого события s0=e и всевозможных слов вида p1p2...pk т.е. , {s}?=sm, где sm - последний из степеней s, для которого условие ? выполнено; итерация с предусловием ?{s} определяется аналогично. В алгебре А задается событие называемое неопределенным и обозначаемое символом ?. Элементарные события в А - события е, x1, x2,..., xn. Аксиомы алгебры А ниже рассмотрены. Все аксиомы алгебры B и правила вывода в ней сохраняются. Правила вывода, используемые в алгебре А включают правила вывода, принятые в программировании - см., например, [1]. Событие, получаемое применением конечного числа операций алгебры А над элементарными, называется регулярным.
    Имеет место важная теорема Клини [2]: регулярные события и только они представимы в конечных автоматах.
    Рассмотрим задачу построения алгоритма регуляризации во введенной паре алгебр (А,B). Алгоритм в укрупненных шагах состоит в следующем.
    Шаг 1. Задается произвольное событие s=s0 s1 s2...sn+1, где si - событие номер i, начальное событие - s0, конечное - sn+1, остальные события - преобразователи и/или события - распознаватели.
    Шаг 2. Составляется система уравнений алгебры событий А: записывается функция F события, его дерево D и дерево состояний определяющее все к путей выполнения : , где Fi - функция ветви дерева состояний. Функция ветви дерева - композиция всех функций (событий) данной ветви; программная функция F - объединение всех функций ветвей дерева.
    Шаг 3. Система уравнений с помощью подстановок и операций дизъюнкции и конъюнкции представляется в виде : X=XA+B, где X - событие, представленное заключительным состоянием sn+1, .
    Шаг 4. Находим решение системы. Используется теорема [3]: если характеристический граф матрицы А (орграф соединяющий ребрами вершины i и j только тогда, когда e?aij) не содержит ни одного цикла, то система X=XA+B имеет единственное решение X=B{A}, которое регулярно при регулярных A, B. При решении системы эффективно преобразовывать уравнения, - как и при решении линейных алгебраических уравнений, например, брать дизъюнкцию событий, изменять порядок исключения событий и др.
    Шаг 5. По условиям выполнимости событий находим регулярную форму этого решения. Используются аксиомы алгебры логики В и соотношения алгебры событий А, например, следующие (AB=A?B, ????????(A) - условие выполнимости события А, A? - проверка условия ? после события А и для этого условия верны все аксиомы алгебры В, - отрицание условия ?):
    Ae=eA=A,
    e?=?(e)=?,
    A?=?A=?,
    2(A+B)=?,
    ?(?(A))=?,
    A(BC)=(AB)C,
    ?(A+B)=(?(A)+ (B)),
    ?(?(A+B))=(??(A))+( (B)),
    ?(A+B)C=?(AC+BC),
    A?(B+C)=?(AB+AC),
    ?(AB)=?(A)B?(B),
    (AB)?=A(B?),
    A{B}?={BA?}A,
    ?({A}?)={A?}?,
    {A}?=?(e+A{A}?),
    {?(A)}(B)={A}B,
    ?{A}?{A}=?{A},
    {? ?{A}}=?{A},
    {A}?{A}?={A}?,
    {{A}??}={A}? ,
    {?(A)}={A} ,
    {A}?+e=?{A},
    A?{A}=?{A}A={A}? .
    Пример 1. ............