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

• Филькин, Андрей Владимирович
• кандидат физико-математических наук
• 2002

Оглавление диссертации кандидат физико-математических наук Филькин, Андрей Владимирович

ВВЕДЕНИЕ

ГЛАВА 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 страницах.

Список литературы диссертационного исследования кандидат физико-математических наук Филькин, Андрей Владимирович, 2002 год

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: [e-mail].

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.