Алгебраические свойства асинхронных автоматов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВЕДЕНИЕ

ГЛАВА 1. Подавтоматы асинхронных автоматов

§1.1. Основные понятия и вспомогательные конструкции

§1.2. Подавтоматы асинхронных автоматов с двумя входными сигналами.

§1.3. Дистрибутивные решетки как решетки подавтоматов асинхронных автоматов.

ГЛАВА 2. Конгруэнции асинхронных автоматов

§2.1. Асинхронные конгруэнции автоматов.

§ 2.2. Конгруэнции асинхронных автоматов.

ГЛАВА 3. Эндоморфизмы и автоморфизмы асинхронных автоматов.

§3.1. Моноиды эндоморфизмов асинхронных автоматов

§3.2. Группы автоморфизмов асинхронных автоматов

Предлагаемая работа посвящена изучению алгебраических свойств асинхронных автоматов, введенных в рассмотрение Кузнецовым О.П. [28] в 1965 году.

Конечным детерминированным автоматом с выходом называется пятерка А = (S, X, Y, 5, X), где S, X, Y — произвольные конечные непустые множества, называемые соответственно множеством состояний, множеством входных сигналов и множеством выходных сигналов автомата, отображение 8: S х X —>S называется функцией переходов автомата, а отображение A,: S х X —> Y — функцией выходов.

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

Автомат А функционирует в дискретной временной шкале по следующему правилу [5]: если s е S — состояние автомата А в данный момент и на его вход подан сигнал х е X, то в следующий момент времени автомат перейдет в состояние 8(s, х) и выдаст на выходе сигнал X(s, х).

Если функция переходов и функция выходов автомата определены для всех пар из S х X, то автомат А называется всюду определенным, в противном случае автомат А называется частичным [14].

Конечным детерминированным автоматом без выхода называется тройка А = (S, X, 5), где S, X и 5 несут тот же смысл, что и в автомате с выходом.

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

Теория автоматов — развитая математическая теория с достаточно широкой тематикой задач. К настоящему времени в ней отчетливо наметились (см. [38]) два аспекта: комбинаторный аспект и алгебраическая теория. Комбинаторный аспект теории автоматов в большей степени связан с поведением, анализом и синтезом автоматов. Этот подход нашел отражение в книгах В.М. Глушкова [15], В.Б. Кудрявцева, С.В. Алешина и

A.С. Подколзина [27], Брауэра [10] и др. Алгебраической теории автоматов посвящены работы A.M. Богомолова и В.Н. Салия [5], Г.М. Бродского [11], Б.И. Плоткина, Л.Я. Гринглаз и А.А. Гварамия [38], Арбиба [1] и др. Комбинаторный и алгебраический аспекты теории автоматов тесно взаимосвязаны. Абстрактно - алгебраические методы находят важные применения в теории языков [31] и алгоритмов (см. работы

B.М. Глушкова [14], [15]), в теории декомпозиции автоматов (статьи на эту тему имеются в [1]). В книге М.А. Спивака [44] алгебраические и комбинаторные вопросы теории автоматов исследуются на базе алгебраической теории бинарных отношений.

Автомат А = (S, X, 5) называется автономным, если X является одноэлементным множеством: Х={х}. В дальнейшем автономные автоматы будем записывать в виде А = (S, 5) и рассматривать 6 как отображение множества S в себя, то есть 5: S —> S. Пусть А = (S, X, 5) — некоторый автомат. Для фиксированного входного сигнала хеХ определим функцию 6Х на множестве S так, что 5Х: s —> 5(s, х). Автономные автоматы Ах = (S, 6Х), хеХ, называются автономными компонентами автомата А.

При алгебраическом подходе автомат в первую очередь рассматривается как алгебраическая структура и становится объектом алгебраической теории. При этом автомат А = (S, X, §) трактуется как конечная унарная алгебра вида А = (S, {5Х | х е X}). Как отмечает В.Н. Салий [40]: представление об автомате без выхода как о конечной унарной алгебре позволяет применить в теории автоматов хорошо разработанные универсально - алгебраические средства, придать установленным с их помощью фактам естественную автоматную трактовку.

Вопросы алгебраической теории частичных автоматов рассматривались, например, в работах Ю.И. Соркина [42] (автоматы без выхода) и Д.Е. Черного [46] (автоматы с выходом). Изложению алгебраической теории вполне определенных автоматов без выхода посвящена книга В.Н. Салия [40], а алгебраической теории вполне определенных автоматов с выходом - книга Б.И. Плоткина, Л.Я. Гринглаза и А. А. Гварамии [38].

Наряду с изучением автоматов вида А = (S, X, 5) в алгебраической теории автоматов активно исследуются автоматы, на множестве состояний и/или на множестве входных сигналов которых определена некоторая алгебраическая структура (набор операций, отношений, подмножеств и т.д.), а функция переходов 8 удовлетворяет тем или иным дополнительным условиям (часто это вызвано желанием получить решение для частного случая проблем, общее решение которых сложно или неизвестно). Автомат с выходом также допускает аналогичное обобщение. Данная тенденция в теории автоматов была подмечена В.М. Глушковым еще в самом начале 60-х годов (см. [14]). В наиболее общем виде автоматы указанного вида изучались в статьях JI.A. Скорнякова [43], А.А. Болотова [6] и др.

Пусть А = (S, X, 5) — некоторый автомат. Состояние seS автомата А называется устойчивым, если 6(s, хх) = 5(s, х) для всех хеХ. Автомат А называется асинхронным, если все его состояния являются устойчивыми [28].

Асинхронные автоматы являются математической моделью дискретного устройства преобразования информации, построенной с учетом неодновременности переключения состояний реальных элементов автоматной схемы при изменении входного сигнала, а также неодновременности изменения состояния входных сигналов (см. [41]). Интуитивно определение асинхронного автомата означает, что он изменяет свое состояние только после изменения входов.

Асинхронным автоматам посвящена достаточно обширная литература как отечественных, так и зарубежных (см. [68]) авторов. Как отмечает Ангер [2], одной из ранних работ по асинхронным последовательностным схемам является работа Кейстера, Ричи и Уошберна [63], основы современного подхода к асинхронным схемам были заложены Хафменом [62].

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

Так в структурной теории автоматов понятие асинхронного автомата используется обычно на этапе надежностного структурного синтеза автомата для более детального изучения переходных процессов (см. [48], [49]), которые могут возникать в сетях из автоматов и, в частности, выявления возможности возникновения гонок, рисков и других явлений, приводящих к неустойчивым переходам или немонотонным изменениям выходных сигналов.

Структурный подход в теории асинхронных автоматов нашел свое отражение в целом ряде работ. Вопросам синтеза асинхронных автоматов посвящены монографии Э.А. Якубайтиса [47], [50], В.Г. Лазарева, Е.И. Пийля [30] и др. Вопросы минимизации, кодирования и анализа асинхронных автоматов изучаются в работах Ангера [2], Миллера [34]. Обзор неклассических моделей асинхронного конечного автомата содержится у А.Ф. Петренко [35].

В.Б. Кудрявцев, А.С. Алешин, А.С. Подколзин [27] приводят следующие формализации модели асинхронного дискретного устройства: асинхронный автомат первого типа А = (S, X, Y, 5, Я), по определению такой, что функция переходов удовлетворяет тождеству 5(s, хх) = 5(s, х), seS, хеХ. Такие автоматы реагируют лишь на изменение входного сигнала, рассматривая цепочки идущих подряд одинаковых входных сигналов как один сигнал. Асинхронный автоматы второго типа А — (S, X, Y, 8, X), по определению, такой, что функция выходов X отображает S х X в Y*. Отличительной особенностью таких автоматов является то, что на каждый входной сигнал асинхронный автомат реагирует, вообще говоря, некоторой цепочкой выходных символов (быть может, пустой). Для асинхронных автоматов второго типа Р.И. Григорчук и В.В. Некрашевич [16] определили группу асинхронных автоматов и установили независимость изоморфного типа этой группы от алфавита, что позволило определить группу рациональных гомеоморфизмов множества Кантора.

Зиелонка [75] рассматривал асинхронный автомат (сеть из конечных автоматов (процессов) с распределенным управлением) как математическую модель распределенных систем. В терминах асинхронного автомата Зиелонка получил характеризацию распознаваемых подмножеств свободного частичного коммутативного моноида (см. работы [52], [54], [65], в которых имеется дальнейшая библиография).

Штарке и Тиле [70] рассматривали асинхронные стохастические автоматы и вопросы сводимости общего асинхронного автомата к некоторым частным видам (автомату Мура). Липтон, Милнер и Снайдер [66] ввели одномерные итеративные сети конечных автоматов, в которых переходы автоматов могут иметь различную длительность (в дискретном времени), ограниченную сверху некоторой константой -задержкой; предложено описание работы такой сети асинхронной грамматикой. Влад [72] как модель асинхронной логической схемы использовал асинхронный автомат, задаваемый двумя семействами функций из R в {0, 1}, им рассмотрена задача синтеза для таких автоматов. Обзор моделей для спецификации и анализа в асинхронных схемах содержится в [12]. Для формального задания асинхронного процесса (в связи с задачей описания протоколов обмена), в качестве одной из интерпретаций, наряду с сетями Петри, В.И. Варшавский и др. [13] используют асинхронный автомат.

Бржозовски [55] исследовал определенные асинхронные автоматы (характеризующиеся тем, что существует некоторое целое число к > 0 такое, что состояние автомата после подачи больше к последовательных входных сигналов (причем рядом стоящие сигналы отличаются друг от друга) зависит лишь от последних к сигналов) и вопросы реализации таких автоматов асинхронными логическими схемами. Чулик [56] изучал условия, при которых автомат Мили вычисляет k-асинхронную функцию в терминах последовательностных функций (отображений из X* и Y*).

Несмотря на обилие результатов по асинхронным автоматам, исследований по алгебраической теории асинхронных автоматов, функция переходов которых удовлетворяет тождеству S(s, хх) = 8(s, х), не достаточно. Отметим некоторые из них.

В ключевой работе О.П. Кузнецова [28] введены в рассмотрение асинхронные автоматы Мили, описан класс регулярных событий, представимых в асинхронных автоматах, и дан упрощенный алгоритм их синтеза.

Кинни [64] рассматривал различные способы (всего шесть) построения новых асинхронных автоматов из имеющихся. Им получены условия представимости данного асинхронного автомата в виде композиции того или иного вида других, более простых. Эти условия формулируются в терминах существования некоторых специальных разбиений на множестве состояний автомата.

В работе Лю [67] рассмотрена задача о кодировании состояний асинхронного автомата двоичными наборами некоторой, по-возможности, меньшей, длины, при которой отсутствуют критические состязания элементов.

М.М. Кац [22] получил критерий линейной упорядочиваемости асинхронных автоматов.

Бинарное отношение pcSx S называется устойчивым в автомате А = (S, X, §), если

Vsb s2 e S)(Vx e X)((sb s2)ep^ (5(sb x), 5(s2, x)) e p).

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

В ряде теоретических и прикладных задач часто приходится рассматривать автоматы вида А = ((S, р), X, 8), где р - устойчивое в автомате А отношение, удовлетворяющее некоторому набору условий. Автоматы вида А = ((S, р), X, 5), где р - устойчивое в автомате А отношение толерантности, изучали Арбиб [51] и И.П. Ильичева, В.В. Печенкин [19].

Отношение эквивалентности, устойчивое в автомате А, называется конгруэнцией автомата А. Совокупность конгруэнций автомата А образует решетку СопА, являющейся важной характеристикой автомата. Класс задач, связанных с конгруэнциями автомата, довольно широк. Эффективный алгоритм построения решетки СопА предложил Фарр [57]. Маккензи показал, что для всякого автомата существует автомат с четырьмя входными сигналами, имеющий такую же решетку конгруэнций [40, С.42]. С.Р. Когаловский и В.В. Солдатова [24] показали, что всякая конечная решетка представима как решетка конгруэнций частичного автомата с двумя входными сигналами. Известно описание автономных автоматов, у которых решетка конгруэнций является двухэлементной [40, С.38], одноатомной (Йоэли [74]), полумодулярной сверху (Берман [53]), решеткой с дополнениями, модулярной, дистрибутивной, цепью, решеткой Стоуна (JI.A. Скорняков и Д.П. Егорова [17], [18]). Г.Ч. Куринной [29] описал автономные автоматы с изоморфными решетками конгруэнций и нашел условия, при которых такой автомат определяется своей решеткой конгруэнций. Различные соответствия между решетками подавтоматов и решеткой конгруэнций автономного автомата исследовала А.В. Киреева [23]. Решетки конгруэнций автоматов с различными условиями на функцию переходов изучал А.П. Бощенко [9]. Конгруэнции, факторы по которым принадлежат специальным классам, изучал (в терминах автоматных графов) М.А. Кабанов [20]. Слабые конгруэнции и слабые эквивалентности автоматов рассматривал В.А. Плаксин [36], [37].

Гомоморфизм автомата в себя называется эндоморфизмом автомата А. Взаимно однозначный эндоморфизм называется автоморфизмом автомата. Эндоморфизмы автомата А образуют моноид, а автоморфизмы — группу.

Конструктивное описание всех эндоморфизмов автономного автомата получили В.А. Лисковец и В.З. Фейнберг [32], а произвольного автомата — Гржимала-Буссе [61]. В.Н. Салий [39], [40, С. 67] предложил матричные методы для вычисления моноида эндоморфизмов произвольного автомата. Группа автоморфизмов вполне определенного автономного автомата описана В.З. Фейнбергом [45]. Варле[71] и A.M. Бочкин [7] установили критерий коммутативности моноида эндоморфизмов автономного автомата,

A.M. Бочкин [8] описал автоматы указанного вида с сепаративным моноидом эндоморфизмов, a JI.A. Скорняков [69] — автоматы указанного вида, у которых моноид эндоморфизмов регулярен, инверсен или является группой. Характеризацию группы автоморфизмов автомата с двухэлементной решеткой конгруэнции предложил Гретцер [60], а

B.Н. Салий [40, С. 66] описал класс моноидов эндоморфизмов автоматов с двухэлементной решеткой конгруэнций.

Группу автоморфизмов сильно связного автомата изучал Виг [73]. В частности, им показано, что моноид эндоморфизмов сильно связного автомата является группой. В работе Флека [59] исследуется связь группы автоморфизмов сильно связных автоматов и их прямых произведений. Фейхтингер [58] рассматривал связи между максимальными сильно связными подавтоматами автомата и их группами автоморфизмов. Один из эффективных алгоритмов построения группы автоморфизмов конечного автомата предложил Ю.Г. Карпов [21].

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

Работа состоит из введения, трех глав, содержащих семь параграфов, и библиографии, включающей 84 наименования. Диссертация изложена на 119 страницах.

1. Алгебраическая теория автоматов, языков и полугрупп / Под ред. М.А. Арбиба. -М.: Статистика. - 1975.

2. Аигер С. Асинхронные последовательностные схемы.— М.: Наука. 1977.

3. Артамонов В.А., Салий В.Н., Скорняков J1.A., ШевринЛ.Н., Шульгейфер Е.Г. Общая алгебра. М.: Наука. - 1991. - Т.2.

4. Биркгоф Г. Теория решеток. М.: Наука. - 1984.

5. Богомолов A.M., Салий В.Н. Алгебраические основы теории дискретных систем. -М.: Наука. 1997.

6. Болотов А.А. Автоматы над алгебрами и задача о неотличимости состояний // Логико-алгебраические конструкции. Калинин. - 1987. -С. 12-16.

7. Бочкин A.M. Унары с коммутативным моноидом эндоморфизмов // Свойства полугрупп. Ленинград. - 1984. — С. 3 - 14.

8. Бочкин A.M. Унары с сепаративным моноидом эндоморфизмов // Изв. вузов. Математика. 1983. - № 5. - С. 71 - 74.

9. Бощенко А.П. Решетки конгруэнций унарных алгебр с двумя операциями f и g, удовлетворяющими тождествам f(g(x)) = g(f(x)) = х или g(f(x)) = х. Волгоград: Волгогр. гос. пед. ун-т, 1998. - 32с.; Деп. в ВИНИТИ 20.04.98, № 1220 - В98.

10. БрауэрВ. Введение в теорию конечных автоматов. М.: Радио и связь. - 1987.

11. Бродский Г.М. Алгебраическая теория автоматов.-Ярославль: Яросл. гос. ун-т. 1988.

12. Варшавский В.И., Кишиневский М.А., Кондратьев А.Ю, Розенблюм Л.Я., ТаубинА.Р. Модели для спецификации и анализа процессов в асинхронных схемах // Изв. АН СССР. Техническая, кибернетика. 1988. - № 2. - С. 171 - 190.

13. Варшавский В.И., Мараховский В.Б., Песчанский В.А., Розенблюм Л.Я. Асинхронные процессы. I. Определение и интерпретация // Изв. АН СССР Техническая кибернетика. 1980. - № 4. - С. 137 - 142.

14. Глушков В.М. Абстрактная теория автоматов // Успехи мат. наук.1961.- Т.16, №5(101). С. 3 - 62.

15. Глушков В.М. Синтез цифровых автоматов. -М.: Наука. 1962.

16. Григорчук Р.И., В.В. Некрашевич. Группа асинхронных автоматов и рациональные гомеоморфизмы множества Кантора//Математические заметки. 2000. - Т.67, вып. 5. - С. 680 - 685.

17. Егорова Д.П. Структура конгруэнций унарной алгебры//Упорядоч. множества и решетки. Вып. 5. 1978. - С. 11 - 44.

18. Егорова Д.П., Скорняков JT.А. О структуре конгруэнций унарной алгебры // Упорядоченные множества и решетки. Вып. 4. — Саратов, 1977. С. 28-40.

19. Ильичева И.П., Печенкин В.В. Контроль структурных автоматов по стабильным отношениям // Методы и сист. технич. диагностики. Вып. 5. Саратов. - 1985. - С. 35 - 43.

20. Кабанов М.А. О конгруэнциях ориентированных графов // Теоретические задачи информатики и ее приложений-Сарагов, 1998.-Вып. 2.-С.49-59.

21. Карпов Ю.Г. О группе автоморфизмов конечного автомата // Автоматика и телемеханика. 1973. - № 8. - С. 70 - 74.

22. Кац М.М. Критерий линейной упорядочиваемости асинхронного автомата. Саратов: Саратов, гос. ун-т, 1997. - 21с.; Деп. в ВИНИТИ 08.05.97, № 1562-В97.

23. КирееваА.В. О некоторых соответствиях между решеткой подавтоматов и решеткой конгруэнций автомата // Упорядоченные множества и решетки. Вып. 10. Саратов, 1991. - С. 51 - 56.

24. Когаловский С.Р., СолдатоваВ.В. О решетках конгруэнций частичных алгебр. II И Упорядоч. множества и решетки. Вып. 10 Саратов.1991.-С. 56-69.

25. Кон П. Универсальная алгебра. М. Мир. - 1968.

26. Кривой C.JI. Алгоритмы вычисления конгруэнтных замыканий конечных автоматов и некоторые их приложения // Кибернетика и системный анализ. 1994 - №1. - С.34 - 44.

27. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. М.: Наука. - 1985.

28. Кузнецов О.П. Представление регулярных событий в асинхронных автоматах // Автоматика и телемеханика. 1965, T.XXVI. - № 6. -С. 1086- 1093.

29. Куринной Г.Ч. Об определимости унара конгруэнциями // Изв. вузов. Математика. 1981. - № 3 (226). - С. 76 - 78.

30. Лазарев В.Г., Пийль Е.И. Синтез асинхронных конечных автоматов.-М.: Наука. 1965.

31. Лаллеман Ж. Полугруппы и комбинаторные приложения. М.: Мир. - 1985.

32. Лисковец В.А., Фейнберг В.З. О перестановочности отображений // ДАН БССР. 1963. - Т.VII, № 6. - С. 366 - 369.

33. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука. - 1971.

34. Миллер Р. Теория переключательных схем. М.: Наука. - 1971. -Т. 2.

35. Петренко А.Ф. Модели асинхронного конечного автомата // Автоматика и вычислительная техника. 1973. - № 4. - С. 1-13.

36. ПлаксинВ.А. Конгруэнции конечных автоматов//Кибернетика.-1982. -№ 1,-С. 43-46.

37. Плаксин В.А. Слабая эквивалентность конечных автоматов // Изв. АН СССР. Техническая кибернетика. 1979. - № 6. - С. 117 - 122.

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

39. СалийВ.Н. О булевозначных автономных автоматах//Методы и системы технич. диагностики. Вып. 6. Саратов. - 1987. - С. 53 - 59.

40. Салий В.Н. Универсальная алгебра и автоматы. Саратов. - 1988.

41. Словарь по кибернетике / Под ред. В.М. Глушкова. Киев. - 1979 -С. 34-35.

42. Соркин Ю.И. Теория определяющих соотношений для автоматов // Проблемы кибернетики. М.: Наука. - 1963, Вып. 9. - С. 45 - 69.

43. Скорняков Л.А. Об алгебраических автоматах//Кибернетика. 1974. -№2- С. 31 -34.

44. Спивак М.А. Введение в абстрактную теорию автоматов. -Саратов. 1970.

45. ФейнбергВ.3. Унарные алгебры и их группы автоморфизмов //ДАН БССР. 1969.-Т. XIII, № 1.-С. 17-21.

46. Черный Д.Е. Алгебраические свойства частичных автоматов // Изв. вузов. Математика. 1970. - № 2. - С. 94 - 99.

47. Якубайтис Э.А. Асинхронные логические автоматы. Рига: изд-во Зинатне. - 1966.

48. Якубайтис Э.А. Асинхронный логический автомат // Автоматика и вычислительная техника. 1967. - № 1. - С. 5 - 9.

49. Якубайтис Э.А. Обобщенная асинхронная модель конечного автомата // Автоматика и вычислительная техника 1969 - № З.-С. 1-5.

50. Якубайтис Э.А. Синтез асинхронных конечных автоматов. Рига: изд-во Зинатне. - 1970.

51. ArbibM. Tolerance automata // Kybernetika.-1967,V. 3.-№3.-P.223-233.

52. Arnold A. An extention of the notions of traces and of asynchronous automata//Theoretical Informatics and Applications. 1991, V. 25. -№4.-P. 355 -393.

53. Berman J. On the congruence lattices of unary algebras // Proc. Amer. Math. Soc. 1972. - V.36, № l.-P. 34-38.

54. Bertoni A., Mauri G., Pighizzini G., Sabadini N. Algebraic and informational aspects of Zielonka's Theorem. In C. Bonzini, A. Cherubini, and C. Tibiletti (eds.), Semigroups. World Scientific, 1993. - P. 17 - 26.

55. Brzozowski Janusz A., Singh Shanker. Definite asynchronous sequential circuits // IEEE Trans. Comput. 1968, V. 17. - № 1. - P.l 8 - 26.

56. Culik K. Asynchronous automata // Computing 1970, V. 6. - № 1-2. -P. 191 - 199.

57. FarrE.H. Lattice properties of sequential machines//J.Assoc. Comput. Mach.- 1963. Y. 2, № 2. - P. 97 - 109.

58. Feichtinger G. Some results on the relation between automata and their automorphism groups // Computing. 1966, V. 1. - № 4. - P. 327 - 340.

59. Fleck A.C. On the automorphism group of an automaton // J. Assoc. Comput. Mach. 1965, V. 12. - № 4. - P. 566 - 569.

60. Gratzer G. On endomorphism semigroup of simple algebras // Math. Ann.1976, V. 170.-№4.-P. 334-338.

61. Grzymala-Busse J.W. Operation-preserving functions and autonomous factors of finite automata//J. Comput. and System Sciences-1971, V.5.-P.465 -474.

62. Huffman D.A. The synthesis of sequential switching circuits // Journal of the Franklin Institute. 1954, V. 257. - № 3. - P. 161 - 190, № 4. - P.275- 303.

63. KeisterW., Ritchie A.E., Washburn S.H. The design of switching circuits. D. VanNostrand, Princeton, N.Y. 1951.

64. Kinney Larry L. Decomposition of asynchronous sequential switching circuits // IEEE Trans. Comput. 1970, V. 19. - № 6 - P. 515 - 519.

65. Lipton R.J., Milner R.E., Snyder L. Synchronization and computing capabilities of linear asynchronous structures // J. Comput. and Syst. Sci.1970, V. 14.-№ l.-P. 49-72.

66. Liu C.N. A state variable assignment method for asynchronous sequential switching circuits.// J. Assoc. Comput. Mach. 1963, V. 10, № 2. -P. 209-216.

67. Peeters A. "The "Asynchronous" Bibliography (BiBTEX) database file async.bib." http://www.win.tue.nl/~wsinap/doc/async.bib. Corresponding e-mail address: async-bib@win.tue.nl.

68. Skornjakov L.A. Unary algebras with regular endomorphism monoid// Acta Sci. Math. 1978, V.40.-№ 3 - 4. - P. 375-381.

69. Starke Peter H., Thiele Helmut. On asynchronous stochastic automata // Inform, and Cont. 1970, V. 17. - № 3. - P. 265 - 293.

70. Yarlet J.C. Endomorphisms and fully invariant congruences in unary algebras // Bull. Soc. Roy. Sci. Liege. 1970, V. 39. - № 11-12.-P.576-585.

71. YladS.E. Selected topics in asynchronous automata//Analele Universitatii Din Oradea, Fascicola Mathematica, Tom VII. 1999.

72. Weeg G.P. The structure of an automaton and its operation-preserving transformation group // J.Assoc. Comput. Mach 1962 - V. 9. - P. 345-349.

73. Yoely M. Subdirectly irreducible unary algebras // Amer. Math, Monthly.1967.- V. 74, № 8. P. 957 - 960.

74. Zielonka W. Notes on finite asynchronous automata // RAIRO, Inf. Theor. Appl. 1987. - Y. 21. - P. 99- 135.118Результаты диссертации опубликованы в следующих работах:

75. Филькин А.В. Описание асинхронных конгруэнций автономного автомата без выхода// Теоретические проблемы информатики и ее приложений. Вып. З.-Саратов: ГосУНЦ «Колледж», 1999. С.137 - 139.

76. Филькин А.В. О решетке асинхронных конгруэнций автомата // Логика и ее приложения (Труды международной конференции, посвященной 60-летию со дня рождения академика Ю.Л. Ершова, Новосибирск, 2000). — Новосибирск, 2000.— С. 103.

77. Филькин А.В. О коммутативных конгруэнциях автомата// Третья международная конференция в Украине, Сумы, 2-8 июля 2001, С.267 -268.

78. Филькин А.В. Построение наименьшей асинхронной конгруэнции автомата без выхода // Теоретические проблемы информатики и ее приложений. Вып. 4. — Саратов: ГосУНЦ «Колледж»,2001.-С. 136-142.

79. Филькин А.В. О решетке конгруэнций асинхронных циклов // Материалы XIII Международной конференции «Проблемы теоретической кибернетики». Часть II.— Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2002.-С. 180.

80. Филькин А.В. О группе автоморфизмов асинхронных циклов //Компьютерные науки и информационные технологии. Тезисы докладов Международной конференции, посвященной памяти профессора A.M. Богомолова.— Саратов: СГУ, 2002.— С.74 75.119

81. Филькин А.В. Конечные дистрибутивные решетки как решетки подавтоматов асинхронных автоматов. — Саратов: СГУ, 2002.- 18 с.; Деп. в ВИНИТИ 14.11.02, № 1972 — В 2002.

82. Филькин А.В. Конечные моноиды как моноиды эндоморфизмов асинхронных автоматов. — Саратов: СГУ, 2002.- 14 с.; Деп. в ВИНИТИ 14.11.02, № 1973—В 2002.