О конкретной характеризации универсальных гиперграфических автоматов

УДК 519.4

E.B. Хворостухина

О КОНКРЕТНОЙ ХАРАКТЕРИЗАЦНИ УНИВЕРСАЛЬНЫХ ГИПЕРГРАФИЧЕСКИХ АВТОМАТОВ

Теория автоматов представляет собой один из основных разделов математической кибернетики, в котором изучаются устройства преобразования информации. В зависимости от специфики рассматриваемых задач устройство преобразования информации может моделироваться автоматом, у которого множество состояний наделено дополнительной математической структурой, сохраняющейся функциями переходов автомата. Так, известные конкретные задачи математической кибернетики приводят к понятиям упорядоченных, линейных, вероятностных, гиперграфических и других автоматов. Исследованиям таких автоматов посвящены, работы Б.И. Плоткина, Р.Г. Бухараева, Л.М. Глускина, Д.В. Сперанского, A.A. Сытника, В.Б. Лендера, A.B. Молчанова и многих других (см., например, [1-3]).

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

Согласно [4] гиперграфом называется алгебраическая система вида H = (X, L), где X - непустое множество вершин гиперграфа и L- семейство произвольных подмножеств X, называемых ребрами гиперграфа. Вершины гиперграфа, содержащиеся в некотором его ребре, называются смежными. Гипергаф H = (X, L) называется эффективным, если любая его вершина содержится в некотором его ребре. Пусть р - произвольное натуральное число. Гиперграф H будем называть гиперграфом с р-определимыми ребрами,

если в каждом его ребре найдется по крайней мерер +1 вершина и, с другой p

Эндоморфизмом гиперграфа H = (X, L) называется преобразование ^ X

в смежные вершины этого гиперграфа. Множество всех эндоморфизмов гиперграфа H с операцией композиции образует полугруппу EndH.

В статье под автоматом понимается полугрупповой автомат без выходных сигналов (см. [1]) A = (X, S, ö) с множеством состояний X, полугруппой входных сигналов S и функцией переходов ö : X х S —> X. Для каждого s Е S отображение ö определяет соответствующую этому входному сигналу

й функцию переходов 53 : X —> X то формуле: 5Дж) = 5(ж,й) (ж £ X). Автомат А = (X, Б, 5) будем называть гиперграфическим, если множество его состояний X наделено такой структурой гиперграфа Н = (X, Ь), что при любом входном сигнале й £ Б функция переходов 5в является эндомор-

Н

Пусть Н = (X, Ь) — произвольный гиперграф и ЕпсШ — полугруппа всех эндоморфизмов Н. Определим отображение 5 : X х EпdH —> X, полагая 5(ж,() = ((ж), где ж £ X и ( £ EпdH. Очевидно, что система Л1ш(Н) = (Н, EndH, 5) является гиперграфическим автоматом. Такой автомат Л1ш(Н) называется универсальным гиперграфическим автоматом над Н,

для всякого гиперграфического автомата А = (Н, Б, 5) существует, и притом единственный, гомоморфизм по входным сигналам этого автомата в автомат ЛШ(Н).

В статье исследована задача конкретной характеризации универсальных гиперграфических автоматов, которая формулируется следующим образом: при каких условиях па множестве состояний автомата А = (X, Б, 5) можно так определить структуру гиперграфа Н = (X, Ь), что будет выполняться равенство А = Л1ш(Н), т.е. полугруппа входных сигналов автомата А будет равна полугруппе эндоморфизмов EndH?

Пусть X - произвольное непустое множество, р - натуральное число и Б произвольная полугруппа преобразований множестваX. Тогда Б определяет па X следующие канонические (р + 1)-арные отношения:

5р = и{(/+1 : ( £ Б};

Яр {(ж1, жp, Жр+1) £ Xp+1 : Xp+1 \ Дх(р + 1) С 5р-1 (жь ..., Жр, Жр+1)},

где Дх(п) = {(ж1,..., жп) £ X" : ж = ж^ для некоторых 1 < г = ] < п}.

Полугруппу Б условимся называть п-ограниченно замкнутой, если она удовлетворяет следующему условию: полугруппа Б содержит все такие преобразования ( множества X, что для любого п-элементного подмножества У С X выполняется равенство (|У = ^|У при некотором ^ £ Б.

Теорема. Автомат, А = (X, Б, 5) без равнодействующих входных сигналов в том и только том случае будет универсальным гиперграфическим автоматом Л1ш(Н) = (Н, EndH, 5) для некоторого эффективного гиперграфа с р-определимыми ребрами Н = (X, Ь), если полугруппа входных сигналов Б является (р + 1)-ограниченно замкнутой полугруппой и ее каноническое отношение Яр удовлетворяет следующим условиям:

(Т1) (ж,..., ж, ж) £ Яр для любо го ж £ X;

(T2) для любых 1 < ¿i,..., ip, ip+i < p +1

(xi,xp+i) Е Rp (x«i,xip, ) Е (T3) для любых попарно различных элементов x1,..., xp Е X

(x xi,xp), (xp, xi,y) Е Rp у (x xi,1, у) Е

(T4) для любых xi,...,xp Е X, удовлетворяющих условию (x^..,xp,xp) Е Rp, найдется такой отличный от всех них элемент x Е X, что (xi, Xp , Х) Е Rp.

Полученный результат дает алгоритм решения задачи о том, какой конечный автомат является универсальным гиперграфическим автоматом для

p

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Плоткип Б.И., Гринглаз Л.Я., Гварамия A.A. Элементы алгебраической теории автоматов. М,: Высш. шк,, 1994.

2. Лендер В. Б. Об эндоморфизмах проективных геометрий // Исследования алгебраических систем: Мат. записки Урал, ун-та. Свердловск, 1984. С. 48-50.

3. Молчанов A.B. Об определяв мости гиперграфических автоматов их выходными функциями // Теоретические проблемы информатики и ее приложений. Саратов, 1998. Вып. 2. С. 74-84.

4. Зыков A.A. Гиперграфы // УМН. 1974. Т. 29, №6. С. 89-154.

УДК 519.642.8

A.A. Хромов

ПРИБЛИЖЕНИЕ РЕШЕНИЙ ИНТЕГРАЛЬНОГО УРАВНЕНИЯ ПЕРВОГО РОДА С ПОМОЩЬЮ СУММ ФЕЙЕРА

В данной статье результаты, полученные в [1] для простейшего интегрального уравнения первого рода, обобщаются на интегральное уравнение Вольтерра.

Рассмотрим уравнение

X

Аи = А