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

• Хворостухина, Екатерина Владимировна
• кандидат физико-математических наук
• 2011

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

Введение

1 Основные понятия

1.1 Элементы алгебры отношений, теории полугрупп и теории гиперграфов

1.2 Гиперграфические автоматы.

1.3 Обратимые входные сигналы универсальных гинерграфических автоматов.

2 Универсальные гиперграфические автоматы

2.1 Определяемость гинерграфических автоматов полугруппами их входных сигналов.

2.2 Конкретная характеризация универсальных гиперграфических автоматов.

2.3 Абстрактная характеризация универсальных гиперграфических автоматов.

3 Взаимосвязь свойств автоматов и их полугрупп входных сигналов

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

3.2 Элементарная эквивалентность универсальных гиперграфических автоматов.

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

3.4 Гомоморфизмы универсальных гиперграфических автоматов.

3.5 Мономорфизмы универсальных х'иперграфических автоматов.

Введение диссертации (часть автореферата) на тему «Логико-алгебраические методы теории гиперграфических автоматов»

Работа посвящена развитию алгебраической теории универсальных гинерграфических автоматов. Теория автоматов представляет собой один из основных разделов математической кибернетики, главными объектами изучения которой являются устройства, предназначенные для управления динамическими системами, изменяющими свои состояния иод воздействием сигналов из внешней среды. Примерами таких устройств могут служить электронно-вычислительное. телекоммуникационное оборудование. бытовая техника и т.н. Математической моделью таких устройств является автомат А = (X, Б, 6), который представляет собой двухосновную алгебраическую систему с двумя основными множествами X, 5 и бинарной операцией 5 : X х Б —> X. При этом X называется множеством состояний, Б множеством входных сигналов, 5 функцией иререходов автомата. Отображение 5 для каждого фиксированного 5 £ 5 определяет соответствующее этому входному сигналу б преобразование 63 множества состояний, которое для каждого х £ X указывает состояние (5.5(ж) = 5(х, в), в которое переходит автомат А при входном сигнале в. Последовательное действие входных сигналов £ £ реализуется композицией преобразований^,^. В результате множество ¿> можно рассматривать как полугруппу с ассоциативной бинарной операцией которая взаимосвязана с функцией переходов автомата но формуле: 6(х, б • £) = 8(5(х, для любых х £ X и б, t Е 5.

В зависимости от специфики рассматриваемых задач математической кибернетики, устройства управления динамическими системами могут моделироваться структуризованными автоматами, у которых множества состояний наделены дополнительной математической структурой, сохраняющейся функциями переходов таких автоматов. В качестве таких дополнительных структур могут выступать, например, структуры вероятностного пространства, линейного пространства, топологического пространства, упорядоченного множества и другие. Автоматы, наделенные такими дополнительными структурами, называются [25], соответственно, вероятностными автоматами, линейными автоматами, топологическими автоматами, упорядоченными автоматами. Исследованиям таких автоматов посвящены известные работы Аблаева Ф.М., Бухараева Р.Г., Скорнякова Л.А., Сперанского Д.В., Плоткина Б.И. Ф. Гечега. Акимовой С.А. и многих других. При таком подходе структуризованные автоматы являются объектами исследования алгебраической теории автоматов, которая основывается на фундаментальных понятиях универсальной алгебры [16] и имеет разнообразные приложения к комбинаторным исследованиям автоматов, связанным с их поведением, анализом и синтезом, к теории формальных языков и к другим разделам математической кибернетики [25], [35].

В настоящей работе продолжается исследование структуризованных автоматов: здесь рассматриваются так называемые гииерграфические автоматы, т.е. автоматы, у которых множества состояний наделены дополнительной алгебраической структурой гиперграфа [12]. Поскольку гиперграфы являются естественным обобщением понятий обыкновенного графа, плоскости [14], [31] и разбиения множества, то изучаемые автоматы образуют достаточно широкий и весьма важный класс автоматов, многообразие которых охватывает, в частности, автоматы, у которых множества состояний являются плоскостями (например, проективными или аффинными), а также автоматы, у которых множества состояний разбиваются на классы некоторой эквивалентности. В работе рассматриваются иолугрупповые автоматы, поэтому далее под гииерграфическим автоматом будем понимать иолу групповой автомат А = (X, у которого множество состояний X наделено такой структурой гиперграфа Н — (X, Ь), что при любом входном сигнале в € 3 функция переходов 53 : X —>• X является эндоморфизмом гииерграфа Н. Основное внимание в работе уделяется гииерграфическим автоматам, у которых множества состояний являются гиперграфами особого вида - эффективными гиперграфами с р—определимыми ребрами. В частности, эффективные гиперграфы с 1-определимыми ребрами - это гииерграфы, ребра которых образуют нетривиальное разбиение множества вершин без одноэлементных классов. Кроме того, эффективными гииерграфами с 2-онределимыми ребрами являются конечные плоскости - специальные комбинаторные конфигурации, которые имеют важные приложения в таких разделах прикладной математики, как теория планирования экспериментов, теория кодирования и многие другие (см. например. [19]).

Главное внимание в настоящей работе уделяется так называемым универсальным гииерграфическим автоматам. Особый интерес к этой тематике объясняется тем, что понятие универсального объекта играет центральную роль в многочисленных приложениях теории категорий к теории автоматов. Например, минимальные автоматы являются универсальными притягивающими объектами в категориях эквивалентных между собой автоматов. При изучении гиперграфических автоматов универсальным притягивающим объектом в категории гиперграфических автоматов с фиксированным гинерграфом состояний Н является автомат Atm(Н) = (Н, End if, 5) с гинерграфом состояний Н = (X, L), полугруппой входных сигналов End Н (состоящей из эндоморфизмов гиперграфа Н) и функцией переходов 8{х,ф) = <р(х) (здесь х £ X, (р Е End Н), который называется универсальным гииерграфическим автоматом и удовлетворяет универсальному свойству: для любого гиперграфического автомата А = (Н, S, 8) с гииерграфом состояний Н существует единственный гомоморфизм по входным сигналам А в Atm(Н).

В таком контексте при исследовании автоматов А с гииерграфом состояний Н важную роль играет полугруппа End Н эндоморфизмов гиперграфа Н. Поэтому алгебраическая теория универсальных гипсрграфических автоматов тесно связана с одним из основных разделов современной алгебры - обобщенной теорией Галуа, которая посвящена изучению математических объектов путем исследования некоторых производных алгебр отображений, специальным образом связанных с исходными объектами. В нашем случае изучаемым математическим объектом является универсальный гиперграфичсский автомат Atm(#), производной алгеброй отображений -- его полугруппа входных сигналов Endil. Таким образом, алгебраическая теория гинерграфических автоматов тесным образом связана с общеизвестной задачей определяемое™ математических объектов их эндоморфизмами и автоморфизмами, которая сформулирована в числе прочих актуальных математических проблем в известной книге С. Улама [29].

Проведенные в работе исследования следуют традиционному кругу вопросов обобщенной теории Галуа. Принципиальное значение имеет задача о том, как производная алгебра отображений определяет исходный объект; затем исследуется, какими абстрактными свойствами характеризуется такая производная алгебра отображений; наконец, с помощью полученных результатов изучаются взаимосвязи свойств исходного объекта и его производной алгебры отображений. Такие вопросы для полугрупп эндоморфизмов графов, колец линейных преобразований векторных пространств и других алгебр преобразований весьма успешно исследовались Важениным Ю.М., Плоткиным Б.И., Глускиным JI.M., Михалевым A.B. и другими авторами. Особое внимание в этом направлении уделялось изучению групп автоморфизмов и полугрупп эндоморфизмов графов, для которых Д. Кениг в [37] сформулировал следующую задачу: каким условиям должна удовлетворять группа подстановок из п элементов, чтобы существовал тг-вершинный граф, группа автоморфизмов которого совпадает с этой группой подстановок? Эта известная и до сих пор не решенная задача является частным случаем сложной проблемы конкретной характеризации [36] производных алгебр отображений в обобщенной теории Галуа, т.е. проблемы описания таких условий, при которых алгебра отображений равна производной алгебре отображений изучаемого математического объекта. В этом направлении отдельные продвижения были сделаны М. Краснером [38], Ляпиным Е.С. [20], Б. Йонсоном [36], Бредихиным Д.А. [4] и другими авторами для полугрупп эндоморфизмов релятивов, групп автоморфизмов и инверсных полугрупп частичных автоморфизмов универсальных алгебр.

Класс универсальных гииерграфических автоматов образует категорию, морфизмами которой являются гомоморфизмы таких автоматов. Изучению таких морфизмов в работе уделяется особое внимание, так как гомоморфизмы автоматов играют важную роль в задачах моделирования автоматов [1], [17]. минимизации автоматов [2], [8], факторизации автоматов [3], [13] и многих других.

Принципиальным отличием проведенных в диссертации исследований является положенное в их основу решение задачи конкретной характеризации универсальных гинерграфических автоматов. Эта задача формулируется следующим образом: при каких условиях на множестве состояний X автомата А можно так определить структуру гиперграфа Н — (X, L), что будет выполняться равенство А = Atm(ii), т.е. полугруппа входных сигналов автомата А будет совпадать с полугруппой эндоморфизмов End HI

Главным инструментом решения сформулированной задачи является разработанная Молчановым В.А. [39] техника канонических отношений полугрупп преобразований, которые определяются в исходных полугруппах формулами языка узкого исчисления предикатов (УИП). Как показывают результаты [23], [39], такое решение поставленной задачи дает эффективный метод последовательного изучения взаимосвязи свойств универсальных структуризованных автоматов и их полугрупп входных сигналов.

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

Во второй главе диссертации рассматриваются комбинаторные и логико-алгебраические свойства универсальных гинерграфических автоматов.

В разделе 2.1 исследована задача об абстрактной определяемости универсальных гинерграфических автоматов над эффективными гиперграфами с р—определимыми ребрами своими полугруппами входных сигналов. В разделе 2.2 излагается центральный результат второй главы, который дает решение задачи конкретной характеризации универсальных гинерграфических автоматов над эффективными гиперграфами с ^—определимыми ребрами. В разделе 2.3 получена абстрактная характеристика универсальных гинерграфических автоматов над эффективными гиперграфами с р—определимыми ребрами.

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

В разделе 3.1 доказана относительно элементарная определимость [9] класса таких автоматов в классе всех полугрупп. С помощью этого результата в разделах 3.2, 3.3 исследована взаимосвязь важных проблем алгоритмической разрешимости элементарных теорий классов эффективных гиперграфов с р—определимыми ребрами, классов универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами и классов полугрупп эндоморфизмов этих гиперграфов.

В разделе 3.4 описано строение сюрьективных гомоморфизмов универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами.

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

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

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

Сделаем несколько замечаний технического характера. Основная информация о понятиях и обозначениях, систематически используемых в диссертации, дается в разделе "Основные понятия". Нумерация теорем, лемм и следствий в диссертации сквозная с учетом номера главы, нумерация формул и рисунков сквозная. Например, ссылка "теорема 2.11"означает теорему 2.11 из главы 2.

Основные результаты диссертационного исследования докладывались и обсуждались на Международной алгебраической конференции, посвященной 100-летию со дня рождения Куроша А.Г.(г. Москва, МГУ, 2008 г.), XV Международной конференции "Проблемы теоретической кибернетики"(г. Казань, КГУ, 2008 г.), XXI Международной научной конференции "Математические методы в технике и технологиях ММТТ-21"(г. Саратов, СГТУ, 2008 г.), Международной научной конференции, посвященной 100-летию со дня рождения профессора Вагнера В.В.(г. Саратов, СГУ, 2008 г.), Международной конференции "Мальцевские чтения", посвященной 100-летию со дня рождения Мальцева А.И. (г. Новосибирск, НГУ, 2009 г.), Международной алгебраической конференции, посвященной 80-летию со дня рождения Кострикина А.И.(г. Нальчик, КБГУ, 2009 г.), Международной научной конференции "Компьютерные науки и информационные технологии"(г. Саратов, СГУ, 2009 г.), Международной конференции "Воображаемая логика"Васильева H.A. и современные неклассические логики"(г. Казань, КФУ, 2010 г.), ежегодных научных конференциях механико-математического факультета "Актуальные проблемы математики и механики"(г. Саратов, СГУ, 2008, 2009, 2010 гг.), ежегодных конференциях по итогам научно-исследовательской работы Саратовского государственного социально-экономического университета "Социально-экономическое развитие России: Проблемы, поиски, решения"(Саратов, СГСЭУ, 2008, 2009, 2010 гг.).

1 Основные понятия

В работе используется общепринятая терминология и известные определения из универсальной алгебры [16], [21], алгебры отношений [5], теории полугрупп [15], [20], теории гиперграфов [12] и алгебраической теории автоматов [25]. В этой главе приводятся основные понятия, необходимые для последующего изложения результатов диссертации.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Хворостухина, Екатерина Владимировна

Заключение

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

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

2) получена абстрактная характеристика универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами;

3) доказана относительно элементарная определимость класса универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами в классе всех полугрупп;

4) решены задачи абстрактной и элементарной определяемости универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами своими полугруппами входных сигналов;

5) описана взаимосвязь важных проблем алгоритмической разрешимости элементарных теорий классов эффективных гиперграфов с р~определимыми ребрами, классов универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами и классов полугрупп эндоморфизмов таких гиперграфов;

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Хворостухина, Екатерина Владимировна, 2011 год

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

2. Биркгоф Г., Барти Т. Современная прикладная алгебра. М.: Мир, 1976. - 400 с.

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

4. Бредихин Д.А. Инверсные полугруппы локальных автоморфизмов универсальных алгебр // Сибирск. матем. журнал, 1975. Т.17, N3. С.490-507.

5. Вагнер В.В. Теория отношений и алгебра частичных отображений // Теория полугрупп и ее приложения. Саратов: Изд-во Сарат. гос. ун-та, 1965. Вып. 1. С. 3-178.

6. Важенин Ю.М. Элементарная определяемость и элементарная характеризация классов рефлексивных графов // Изв. вузов. Матем., 1972. N7. С. 3-11.

7. Важенин Ю.М. Элементарные свойства полугрупп преобразований упорядоченных множеств // Алгебра и логика. Новосибирск, 1970. Т.9, N3. С. 281-301.

8. Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966. - 272 с.

9. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. -М.: Наука, 1980. 320 с.

10. Ершов Ю.Л., Палютин Е.А. Математическая логика. М.: Наука. Гл. ред. физ.-мат. лит., 1987. - 336 с.

11. И. Ершов Ю.Л., Лавров И.А., Тайманов А.Д., Тайдлин М.А. Элементарные теории // УМН, 1965. Т. 20, N4. С. 37-108.

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

13. Карпов Ю.Г. Теория автоматов. Спб.: Питер, 2003. - 208 с.

14. Картези Ф. Введение в конечные геометрии: Пер. с англ. М.: Наука. Главная редакция физико-математической литературы, 1980.- 320 с.

15. Клиффорд А., Престон Г. Алгебраическая теория полугрупп. Том 1.- М.: Мир, 1972. 286 с.

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

17. Кудрявцев В.Б., Алешин C.B., Подколзин A.C. Введение в теорию автоматов. М.: Наука, 1985. - 320 с.

18. Лендер В.Б. Об эндоморфизмах проективных геометрий // XYI Всесоюзн. алг. конф. Тезисы докл., 1981. 4.2. С. 82.

19. Лидл Р., Пильц Г. Прикладная абстрактная алгебра: Учеб. пособие/ Пер. с англ. Екатеринбург: Изд-во Урал, ун-та, 1996. - 744 с.

20. Ляпин Е.С. Полугруппы. М.: Физматлит, 1960. - 592 с.

21. Мальцев А.И. Алгебраические системы. М.: Наука, 1970. - 392 с.

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

23. Молчанов A.B. Полугруппы эндоморфизмов слабых р—гиперграфов // Известия вузов. Математика, 2000. N3(454). С. 80-83.

24. Молчанов В.А. Как проективные плоскости определяются своими полугруппами // Теория полугрупп и ее приложения. Полугруппы и связанные с ними алгебраические системы. Саратов: Изд-во Сарат. гос. ун-та, 1984. С. 42-50.

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

26. Робинсон А. Введение в теорию моделей и математику алгебры. -М., 1967. 376 с.

27. Свердловская тетрадь: Сб. нерешенных задач по теории полугрупп. Свердловск: Изд-во Урал. гос. ун-та, 1979. - 238 с.

28. Справочная книга по математической логике в 4-х частях под ред. Дж. Барвайса. Часть 3. Теория рекурсиии: пер. с англ. М.: Изд-во физ.-мат. лит-ры, 1982. - 360 с.

29. Улам С. Нерешенные математические задачи. М.: Наука, 1964. -168 с.

30. Уилсон Р. Введение в теорию графов. М.: Мир, 1977. - 207 с.

31. Хартсхорн Р. Основы проективной геометрии. М.: Мир, 1970. -161 с.

32. Ах J. Solving diophantine modulo every prime // Ann. Math, 1967. N35. P. 161-183.

33. Church A. A note on the Entscheidungs problem // J. S. L., 1936. N1. P. 40-41.

34. Church A. An unsolvable problem of elementary number theory // Amer. Journ. of Math, 1936. N58. P. 345-363.

35. Eilenberg S. Automata, languages and machines. Vol.B. New York, San Francisco, London: Academic Press, 1976. - 387 p.

36. Jonsson B. Topics in universal algebra. Lecture Notes in Math. Berlin, Heidelberg, New York: Springer-Verlag, 1972. N250. - 220 p.

37. D.Konig. Theorie der endlichen und unendlichen Graphen. Leipzig, 1936. - 190 p.

38. Krasner M. Endotheorie de Galois abstraktion // Semin. Dubriel, Dubriel-Jacotin, Lesieur et Pisot. Fac. sei. Paris, 1968-1969(1970). V.22, N1. S.6/01-6/19.

39. Molchanov V. A. Semigroups of mapping s on graphs // Semigroup Forum 27, 1983. P. 155-199.

40. Rosser J. B. Extensions of some theorems of Godel and Church // J. S. L., 1936. N1. P. 87.

41. Tarski A. A Decision Method for Elementary Algebra and Geometry. 2nd revised. Berkeley, Los Angeles, 1951. - 289 p.

42. Публикации автора по теме диссертации.

43. А2. Хворостухина Е.В. Об определяемое™ гиперграфических автоматов полугруппами их входных сигналов // XV международная конференция "Проблемы теоретической кибернетики". Тезисы докладов.- Казань: изд-во Казанского гос. ун-та, 2008. С. 121.

44. А4. Хворостухина Е.В. О моделировании гиперграфических автоматов // Математические методы в технике и технологиях -ММТТ-21: сб.трудов XXI Международ, науч. конф.: в 10 т. Саратов: Сарат.гос.техн.ун-т, 2008. Т.1. С. 86-88.

45. Аб. Хворостухина Е.В. О конкретной характеризации универсальных гиперграфических автоматов // Математика. Механика: Сб.науч. тр. -Саратов: Изд-во Сарат. ун-та, 2008. Вып. 10. С. 151-154.

46. А7. Хворостухина Е.В. Об одном классе гиперграфических автоматов // Теоретические проблемы информатики и ее приложений: сб.науч.тр.- Саратов: Изд-во Сарат. ун-та, 2008. Вып.8. С. 112-118.

47. А8. Хворостухина Е.В. Построение плоскости. М.: ВНТИЦ, 2008. -N 50200802489.

48. А9. Хворостухина Е.В. О конкретной характеризации универсальных гиперграфических автоматов / / Фундаментальная и прикладная математика, 2008. Т. 14, N7. С. 223-231.

49. А12. Хворостухина Е.В. Об относительно элементарной определимости класса гиперграфов в классе всех полугрупп // Международная конференция "Мальцевские чтения", поев. 100-летию со дня рождения А.И. Мальцева. Тезисы докладов. Новосибирск, 2009. С. 170.

50. А14. Хворостухина Е.В. О хопфовости полугрупп эндоморфизмов гиперграфов // Алгебра и ее приложения: труды Междун. алгебр, конф., посвящ. 80-летию со дня рожд. А.И. Кострикипа. Нальчик: Каб.-Балк. ун-т, 2009. С. 130-132.

51. А14. Хворостухина Е.В. Об эпиморфизмах гиперграфических автоматов // Математика. Механика: Сб.науч. тр. Саратов: Изд-во Сарат. ун-та, 2009. Вып. 11. С. 82-84.

52. А15. Хворостухина Е.В. О гомоморфизмах полугрупп эндоморфизмов гиперграфов //Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика, 2009. Т. 9, Вып. 3. С. 70-75.

53. А16. Khvorostukhina Е. On concrete characterization of universal hypergraphic automata // Journal of Mathematical Sciences. New York: Springer New York, 2010. Vol. 164, No.2. P. 303-308.

54. А18. Хворостухина Е.В. О мономорфизмах автоматов // Труды

55. Математического центра имени Н. И. Лобачевского: материалы Международной научной конференции "Воображаемая логика"Н. А. Васильева и современные неклассические логики". Казань: Казан, мат. об-во, 2010. Т.41. С. 103-105.