Логико-алгебраические методы теории гиперграфических автоматов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Хворостухина, Екатерина Владимировна
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Саратов
МЕСТО ЗАЩИТЫ
|
||||
|
2011
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
На правах рукописи
Хворостухина Екатерина Владимировна
ЛОГИКО-АЛГЕБРАИЧЕСКИЕ МЕТОДЫ ТЕОРИИ ГИПЕРГРАФИЧЕСКИХ АВТОМАТОВ
01.01.09 - дискретная математика и математическая кибернетика
2 <■ 033 Ш
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Саратов - 2011
4856147
Работа выполнена на кафедре прикладной математики и информатики Саратовского государственного социально-экономического университета.
Научный руководитель: доктор физико-математических наук,
профессор Молчанов Владимир Александрович
Официальные оппоненты: доктор физико-математических наук,
профессор Бредихин Дмитрий Александрович
кандидат физико-математических наук, профессор Карташов Владимир Константинович
Ведущая организация: Казанский (Приволжский) федеральный
университет
Защита состоится "24"февраля 2011 г. в 15 час. 30 мин. на заседании диссертационного совета ДМ 212.243.15 при Саратовском государственном университете имени Н.Г.Чернышевского по адресу: 410012, Саратов, ул. Астраханская, 83, СГУ, IX корпус.
С диссертацией можно ознакомиться в Научной библиотеке Саратовского государственного университета им. Н.Г.Чернышевского.
Автореферат разослан "¿¿¿"января 2011 г.
Ученый секретарь диссертационного совета кандидат физико-математических наук, доцент
В.В.Корнев
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы. Работа посвящена развитию алгебраической теории универсальных гиперграфических автоматов. Теория автоматов представляет собой один из основных разделов математической кибернетики, главными объектами изучения которой являются устройства, предназначенные для управления динамическими системами, изменяющими свои состояния под воздействием сигналов из внешней среды. Примерами таких устройств могут служить электронно-вычислительное, телекоммуникационное оборудование, бытовая техника и т.п. Математической моделью таких устройств является автомат А = (X, 5,6), который представляет собой двухосновную алгебраическую систему с двумя основными множествами X, Б и бинарной операцией <5 : X х 5 -+ X. При этом X называется множеством состояний, 5 - множеством входных сигналов, 6 - функцией переходов автомата. Отображение 5 для каждого фиксированного в & Б определяет соответствующее этому входному сигналу в преобразование ¿в множества состояний, которое для каждого х & X указывает состояние ¿¡¡(ж) = ¿(ж, з), в которое переходит автомат А при входном сигнале е. Последовательное действие входных сигналов £ € 5 реализуется композицией преобразований $а, В результате множество 5 можно рассматривать как полугруппу с ассоциативной бинарной операцией ■, которая взаимосвязана с функцией переходов автомата по формуле: ¿(х, я • £) = ¿(6(х, в), £) для любых х 6 X и в, Ь 6 5.
В зависимости от специфики рассматриваемых задач математической кибернетики, устройства управления динамическими системами могут моделироваться структуризованными автоматами, у которых множества состояний наделены дополнительной математической структурой, сохраняющейся функциями переходов таких автоматов. В качестве таких дополнительных структур могут выступать, например, структуры вероятностного пространства, линейного пространства, топологического пространства, упорядоченного множества и другие. Автоматы, наделенные такими дополнительными структурами, называются [11], соответственно, вероятностными автоматами, линейными автоматами, топологическими автоматами; упорядоченными автоматами. Исследованиям таких автоматов посвящены известные работы Аблаева Ф.М., Бухараева Р.Г., Скорнякова Л.А., Сперанского Д.В., Плотина Б.И., Ф. Гечега, Акимовой С.А. и многих других. При таком подходе структуризованные автоматы являются объектами исследования алгебраической теории автоматов, которая основывается
на фундаментальных понятиях универсальной алгебры и имеет разнообразные приложения к комбинаторным исследованиям автоматов, связанным с их поведением, анализом й синтезом, к теории формальных языков и к другим разделам математической кибернетики [11], [13].
В настоящей работе продолжается исследование структуризованных автоматов: здесь рассматриваются так называемые гиперграфические автоматы, т.е. автоматы, у которых множества состояний наделены дополнительной алгебраической структурой гиперграфа [5]. Поскольку гиперграфы являются естественным обобщением понятий обыкновенного графа, плоскости [6] и разбиения множества, то изучаемые автоматы образуют достаточно широкий и весьма важный класс автоматов, многообразие которых охватывает, в частности, автоматы, у которых множества состояний являются плоскостями (например, проективными или аффинными), а также автоматы, у которых множества соегояний разбиваются на классы, некоторой эквивалентности. В работе рассматриваются полугрупповые автоматы, поэтому далее под гиперграфическим автоматом будем понимать полугрупповой автомат А — (X, Б, 6), у которого множество состояний X наделено такой структурой гиперграфа Н (Х,Ь), что при любом входном сигнале я € ¿> функция переходов : X —5- X является эндоморфизмом гиперграфа Н. Основное внимание в работе уделяется гиперграфическим автоматам, у которых множества состояний являются гиперграфами особого вида - эффективными гиперграфами с р—определимыми ребрами. В частности, эффективные гиперграфы с 1-определимыми ребрами - это гиперграфы, ребра которых образуют нетривиальное разбиение множества вершин без одноэлементных классов. Кроме того, эффективными гиперграфами с 2-определимыми ребрами являются конечные плоскости - специальные комбинаторные конфигурации, которые имеют важные приложения в таких разделах прикладной математики, как теория планирования экспериментов, теория кодирования и многие другие.
Главное внимание в настоящей работе уделяется так называемым универсальным гиперграфическим автоматам. Особый интерес к этой тематике объясняется тем, что понятие универсального объекта играет центральную роль в многочисленных приложениях теории категорий к теории автоматов. Например, минимальные автоматы являются универсальными притягивающими объектами в категориях Эквивалентных между собой автоматов. При изучении гиперграфических автоматов универсальным притягивающим
объектом в категории гиперграфических автоматов с фиксированным гиперграфом состояний Я является автомат Atm(#) = (Я, End Я, S) с гиперграфом состояний Я — (X,L), полугруппой входных сигналов End Я (состоящей из эндоморфизмов гиперграфа Я) и функцией переходов 5(я, <р) = tp(x) (здесь End Я), который называется
универсальным гиперграфическим автоматом над гиперграфом Я.
В таком контексте при исследовании автоматов А с гиперграфом состояний Я важную роль играет полугруппа End Я эндоморфизмов гиперграфа Я. Поэтому алгебраическая теория универсальных гиперграфических автоматов тесно связана с одним из основных разделов современной алгебры - обобщенной теорией Галуа, которая посвящена изучению математических объектов путем исследования некоторых производных алгебр отображений, специальным образом связанных с исходными объектами. В нашем случае изучаемым математическим объектом является универсальный гиперграфический автомат Айп(Я), производной алгеброй отображений - его полугруппа входных сигналов End Я. Таким образом, алгебраическая теория гиперграфических автоматов тесным образом связана с общеизвестной задачей определяемости математических объектов их эндоморфизмами и автоморфизмами, которая сформулирована в числе прочих актуальных математических проблем в известной книге С. Улама [12].
Проведенные в работе исследования следуют традиционному кругу вопросов обобщенной теории Галуа. Принципиальное значение имеет задача о том, как производная алгебра отображений определяет исходный объект; затем исследуется, какими абстрактными свойствами характеризуется такая производная алгебра отображений; наконец, с помощью полученных результатов изучаются взаимосвязи свойств исходного объекта и его производной алгебры отображений. Такие вопросы для полугрупп эндоморфизмов графов, колец линейных преобразований векторных пространств и других алгебр преобразований весьма успешно исследовались Важениным Ю.М., Плоткиным Б.И., Глускиным JI.M., Михалевым A.B. и другими авторами. Особое внимание в этом направлении уделялось изучению групп автоморфизмов и полугрупп эндоморфизмов графов, для которых Д. Кениг в [15] сформулировал следующую задачу: каким условиям должна удовлетворять группа подстановок из п элементов, чтобы существовал n-вершинный граф, группа автоморфизмов которого совпадает с этой группой подстановок? Эта известная и до сих пор не решенная задача является частным случаем сложной проблемы конкретной
характеризации [14] производных алгебр отображений в обобщенной теории Галуа, т.е. проблемы описания таких условий, при которых алгебра отображений равна производной алгебре отображений изучаемого математического объекта. В этом направлении отдельные продвижения были сделаны М. Краснером [16], Ляпиным Е.С. [8], Б. Йонсоном [14], Бредихиным Д.А. [3] и другими авторами для полугрупп эндоморфизмов релятивов, групп автоморфизмов и инверсных полугрупп частичных автоморфизмов универсальных алгебр.
Класс универсальных гиперграфических автоматов образует категорию, морфизмами которой являются гомоморфизмы таких автоматов. Изучению таких морфизмов в работе уделяется особое внимание, так как гомоморфизмы автоматов играют важную роль в задачах моделирования автоматов [2], [7], минимизации автоматов [1], факторизации автоматов [2] и многих других.
Принципиальным отличием проведенных в диссертации исследований является положенное в их основу решение задачи конкретной характеризации универсальных гиперграфических автоматов. Эта задача формулируется следующим образом:
при каких условиях на множестве состояний X автомата А можно так определять структуру гиперграфа Н = (Ху L), что будет выполняться равенство А = Atm(Я), т.е. полугруппа входных сигналов автомата А будет совпадать с полугруппой эндоморфизмов End Я?
Главным инструментом решения сформулированной задачи является разработанная Молчановым В.А. [17] техника канонических отношений полугрупп преобразований, которые определяются в исходных полугруппах формулами языка узкого исчисления предикатов (УИП). Как показывают результаты [10], [17], такое решение поставленной задачи дает эффективный метод последовательного изучения взаимосвязи свойств универсальных сгруктуризованных автоматов и их полугрупп входных сигналов.
Цель работы. Разработать логико-алгебраические методы исследования гиперграфических автоматов. Решить задачу конкретной характеризации универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами. Изучить взаимосвязь свойств универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами со свойствами их полугрупп входных сигналов.
Методы исследования. В работе использовались методы теории автоматов, универсальной алгебры, математической логики, теории
полугрупп и теории гиперграфов.
Научная новизна и выносимые на защиту положения.
Основные результаты диссертации:
1) получено решение задачи конкретной характеризации универсальных гиперграфических автоматов над эффективными гиперграфами с р-определимыми ребрами, которое позволяет по полугруппе входных сигналов такого автомата восстановить весь автомат;
2) получена, абстрактная характеристика универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами;
3) доказана относительно элементарная определимость класса универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами в классе всех полугрупп;
4) решены задачи абстрактной и элементарной определяемое™ универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами своими полугруппами входных сигналов;
5) описана взаимосвязь важных проблем алгоритмической разрешимости элементарных теорий классов эффективных гиперграфов с р—определимыми ребрами, классов универсальных гиперграфических автоматов над эффективными гиперграфами с р~определимыми ребрами и классов полугрупп эндоморфизмов таких гиперграфов;
6) описана взаимосвязь эпиморфизмов универсальных гиперграфических автоматов над эффективными гиперграфами с р~определимыми ребрами с морфизмами полугрупп входных сигналов этих автоматов.
Все вышеназванные результаты являются новыми.
Научная и практическая ценность работы. Диссертация носит теоретический характер. Полученные результаты могут быть использованы в алгебраической теории автоматов, универсальной алгебре, теории гиперграфов и теории полугрупп.
Апробация работы. Основные результаты диссертационного исследования докладывались и обсуждались на Международной алгебраической конференции, посвященной 100-летию со дня рождения
Куроша А.Г.(г. Москва, МГУ, 2008 г.), XV Международной конференции "Проблемы теоретической кибернетики"(г. Казань, КГУ, 2008 г.), XXI Международной научной конференции "Математические методы в технике и технологиях ММТТ-21" (г. Саратов, СГТУ, 2008 г.), Международной научной конференции, посвященной 100-летию со дня. рождения профессора Вагнера В.В.(г. Саратов, СГУ, 2008 г.), Международной конференции "Мальцевские чтения", посвященной 100-летию со дня рождения Мальцева А.И.(г. Новосибирск, НГУ, 2009 г.), Международной алгебраической конференции, посвященной 80-летию со дня рождения Кострикина А.И.(г. Нальчик, КБГУ,
2009 г.), Международной научной конференции "Компьютерные науки и информационные технологии"(г. Саратов, СГУ, 2009 г.), Международной конференции "Воображаемая логика"Васильева H.A. и современные неклассические логики"(г. Казань, КФУ, 2010 г.), ежегодных научных конференциях механико-математического факультета "Актуальные проблемы математики и механики" (г. Саратов, СГУ, 2008, 2009,
2010 гг.), ежегодных конференциях по итогам научно-исследовательской работы Саратовского государственного социально-экономического университета "Социально-экономическое развитие России: Проблемы, поиски, решения"(Саратов, СГСЭУ, 2008, 2009, 2010 гг.).
..Публикации. Основные результаты опубликованы в работах [А1|-[А18]. Работы [AI] и [А2] опубликованы в изданиях, содержащихся в Перечне ведущих рецензируемых научных журналов и изданий, рекомендованных ВАК.
Структура и объем диссертации. Работа состоит из введения, трех глав, заключения и списка использованной литературы, включающего 42 наименования. Общий объем работы составляет 132 страницы.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность темы и описывается краткое содержание диссертации.
' В разделах 1.1,1.2 первой главы приводятся основные понятия теории гиперграфов, алгебры отношений, теории полугрупп и теории автоматов, ¡которые необходимы для последовательного развития алгебраической теории гиперграфических автоматов. В разделе 1.3 описываются обратимые входные. сигналы универсальных гиперграфических автоматов, чьи множества состояний являются аффинными или проективными плоскостями малых размерностей. /
Согласно [5] гиперграфом называется система вида Н — (Х,Ь), где X - это непустое множество вершин гиперграфа и Ь -семейство некоторых подмножеств множества X, называемых ребрами гиперграфа. Множество вершин гиперграфа называется ограниченным, если оно содержится в некотором его ребре, и неограниченным в противном случае. Вершины гиперграфа, принадлежащие некоторому его ребру, называются смежными. Гиперграф называется эффективным, если любая его вершина принадлежит некоторому ребру этого гиперграфа. -
Пусть р - некоторое натуральное число. Гиперграф Я будем называть гиперграфом с р-определимыми ребрами, если в каждом ребре этого гиперграфа найдется по крайней мерер+1 вершина и, с другой стороны, любые р вершин гиперграфа содержатся не более, чем в одном ребре.
Гомоморфизмом гиперграфа Я = (Х,Ь) в гиперграф Н\ = (Хх, Ь\) называется отображение множества X в множество Х\, которое смежные в гиперграфе Я вершины переводит в смежные вершины гиперграфа Н\. Гомоморфизм гиперграфа Я в себя называется эндоморфизмом. Множество всех эндоморфизмов гиперграфа Я с операцией композиции образует полугруппу Епс1Я. Гомоморфизм / : Я :—У Н\ называется эпиморфизмом гиперграфа Я на гиперграф Ях, если образом множества вершин X гиперграфа Я является все множество вершин Х\ гиперграфа Щ, то есть /(X) = Х1.
Гиперграфы Я = (Х,Ь) и Н\ = (Х1, Ь\) называются изоморфными, если найдется такая биекция / множества X на множество Хь которая сохраняет ребра этих гиперграфов.
Под гиперграфическим автоматом понимается полугрупповой автомат без выходных сигналов А = (X, 5,6), у которого множество состояний X наделено такой структурой гиперграфа Я = (X, Ь), что при любом входном сигнале в £ Б функция переходов 63 : X —>■ X является эндоморфизмом гиперграфа Я. Например, для любого гиперграфа Я алгебраическая система А = (Я, Епс1Я, 6) с функцией переходов = <р(х) (где ц> £ Епс1Я,ж Е X) является гиперграфическим автоматом, который обозначается АХт(Н) и называется универсальнымы гиперграфическим автоматом.
Пусть А = (Я, 5,5) и = (Я1} 5\) - гиперграфические автоматы. Гомоморфизмом автомата А в автомат А\ называется пара отображений 7Г = (/,5)) где / : Я —> Н\, д : 5 —> 5\ - такие гомоморфизмы гиперграфов и полугрупп соответственно, что для любых х 6 X, й € 5 выполняется равенство f(S(x,s)) = ¿х(/(а;),д(в)). Если при
этом / и д являются эпиморфизмами гиперграфов Я, Н\ и полугрупп Б, соответственно, то гомоморфизм 7Г = (/, д) называется также эпиморфизмом автомата А на автомат А\. Если же / ид- изоморфизмы гиперграфов Я, Н\ и полугрупп Б, ^ соответственно, то гомоморфизм 7г = (/, д) называется изоморфизмом автомата Л на автомат А\
Во второй главе диссертации рассматриваются комбинаторные и логико-алгебраические свойства универсальных гиперграфических автоматов.
В разделе 2.1 решена задача об абстрактной определяемости универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами своими полугруппами входных сигналов.
Теорема 2.2. Пусть Я = (X, Ь), Н\ = (Хх, Ь{) - эффективные гиперграфы с р-определимыми ребрами и А1;т(Я), АШ(Я1) - универсальные гиперграфические автоматы над Н, Н\. Тогда полугруппы входных сигналов этих автоматов будут изоморфны в том и только том случае, если изоморфны автоматы А1;т(Я) и А1т(Я1).
В разделе 2.2 излагается центральный результат второй главы, который дает решение задачи конкретной характеризации универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами.
Пусть X - произвольное непустое множество, р - натуральное число и Я - [р 4- 1)-арное отношение на множестве X. Согласно [9] отношение Я называется р-эквивалентностью на множестве X, если оно удовлетворяет следующим условиям:
(Т:) (х,...,х,х) е Я для любого х € Л'; ... . (Тг) для любых 1 < ¿1,..., гр> гр+х < р + 1,
(^ъ хр, Хр+1_) е Я => (х{1,..., х{р+1) е Я;
(Т3) для любых попарно различных элементов ху,хр 6 X,
(я, XI,...,хр-1, хр), (®1,..., агр_1, хр, у) е Я (х, хь..., хр-Ь у) е Я.
При этом р-эквивалентность Я называется квазиполной, если выполняется условие
; (Т4) для любых элементов ...,хр е X, удовлетворяющих условию (жь.:, хр, Хр) € Я, найдется такой отличный от всех них элемент х £ X, что (х1, ..,хр,х) € Я.
Пусть X - произвольное непустое множество, р - натуральное число и 5 - произвольная полугруппа преобразований множества X. Тогда £>
определяет на X следующие канонические (р + 1)-арные отношения:
Sp = üiv^1 : р G S};
Щ = {(ib-.^p.ajH.i) € X^1: \ Ax(p+ 1) С ¿^(xi, ..„х,,^)},
где Дх(п) = {(xi,..., x„) £ Xn : Xi = Xj для некоторых 1 < i ф j < n}.
Полугруппу S преобразований множества X условимся называть n-ограниченно замкнутой, если она содержит все такие преобразования <р множества X, что для любого n-элементного Яр-ограниченного множества У С X выполняется равенство tp\Y = tp\Y при некотором 065.
Решение задачи конкретной характеризации универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами дает следующий результат.
Теорема 2.9. Автомат А — (X, S, 6) без равнодействующих входных сигналов в том и только том случае будет универсальным гиперграфическим автоматом Atm(üT) для некоторого эффективного гиперграфа с р-определимыми ребрами Я = (X, L), если его полугруппа входных сигналов S является (р+1)-ограниченно замкнутой полугруппой и ее каноническое отношение Rp является квазиполной р-эквивалентностью на множестве X.
В разделе 2.3 получена абстрактная характеристика исследуемых в работе универсальных гиперграфических автоматов, которая дает необходимые и достаточные условия, при которых автомат изоморфен универсальному гиперграфическому автомату над некоторым эффективным гиперграфом с р—определимыми ребрами.
В третьей главе диссертации приведены результаты исследования взаимосвязи свойств универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами и полугрупп входных сигналов этих автоматов.
В разделе 3.1 доказана относительно элементарная определимость [4] класса таких автоматов в классе всех полугрупп.
Терема 3.3. Существуют такие формулы С(х), L(x), Eqv(x;y), Ins(x;y) сигнатуры языка элементарной теории полугрупп L§ (здесь и далее х = (хи...,хр), у = {уг,...,ур), У* =' (j/i,■ • • что любой универсальный гиперграфический автомат А = Atm(Я) над эффективным гиперграфом с р~ определимыми ребрами Я = (X, L) и его полугруппа входных сигналов S — Inp(A) удовлетворяют следующим условиям:
1) множества X = {х 6 S : С(х)} и L — {х е Sp : L(x)} не пусты;
2) формула Eqv(i; у) задает отношение эквивалентности Eqv на множестве L;
3) формула Ins(x;j/) задает бинарное отношение Ins между элементами множества X и множества L, которое согласовано с эквивалентностью Eqv по следующей формуле:
(х, х) € Ins Л х = y(Eqv) =4- (х, у) е Ins;
4) автомат А = ((X, L, &), S, 8) изоморфен гиперграфическому автомату А — (Я, 5,<$), где Я = ( X, L/Eqv, ß ) для такого бинарного отношения Ji С X х LjEqv, что
(х, Y) G ~ß (х, х) G Ins, для всех х G У,
и отображение 6 : X х S —> X определяется по формуле 6(х, = х-ф, при любых х е Хи ф € End Я;
5) для любой формулы Ф сигнатуры языка элементарной теории гиперграфических автоматов Ьд эффективно строится такая формула Ф сигнатуры языка элементарной теории полугрупп Ls, что Ф в том и только том случае истинна на универсальном гиперграфическом автомате А для некоторого эффективного гиперграфа с р-определимыми ребрами, если формула Ф истинна на его полугруппе входных сигналов 1пр(А), т.е. выполняется условие: А ¡= Ф <=$» Inp(A) (= Ф.
С помощью этого результата в разделе 3.2 решена задача об элементарной определяемое™ универсальных гиперграфических автоматов своими полугруппами входных сигналов.
Теорема 3.4. Пусть Я, Н\ - эффективные гиперграфы с р—определимыми ребрами и Atm(Я) = А, Atm(Hi) = Ai -универсальные гиперграфические автоматы над Я, Н\ соответственно. Тогда полугруппы входных сигналов этих автоматов элементарно эквивалентны в том и только том случае, если элементарно эквивалентны автоматы А и А\.
С помощью полученной в теореме 3.3 относительно элементарной определимости класса универсальных гиперграфических автоматов над эффективными гиперграфами с р-определимыми ребрами в классе полугрупп в разделе 3.3 исследована взаимосвязь важных проблем алгоритмической разрешимости [4] элементарных теорий классов эффективных гиперграфов с р—определимыми ребрами, классов универсальных гиперграфических автоматов над такими гиперграфами и классов полугрупп эндоморфизмов таких гиперграфов.
Для класса гиперграфических автоматов: К символом 1пр(К) обозначается класс полугрупп входных сигналов автоматов класса К.
Теорема 3.6. Для любого класса К универсальных гиперграфических автоматов над эффективными гиперграфами с р-определимыми ребрами справедливы следующие утверждения:
1) если элементарная теория класса К наследственно неразрешима, то и элементарная теория класса полугрупп 1пр(К) наследственно неразрешима;
2) если элементарная теория класса К эффективно неотделима, то и элементарная теория класса полугрупп 1пр(К) эффективно неотделима.
В разделе 3.4 описано строение, сюрьективных гомоморфизмов универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами.
Обозначим через £ц отношение связности гииерграфа Н [5].
Теорема 3.9. Пусть Atm(#) - универсальный гиперграфический автомат над эффективным гиперграфом с р~определимыми ребрами Я = (X, L), Atm(#i) - универсальный гиперграфический автомат над эффективным гиперграфом с р-определимыми ребрами Hi — (Xi, Li), f - отображение I в Ii и g - отображение End Я в Endi^. Тогда пара отображений 7г — (/, д) в том и только том случае является эпиморфизмом Atm(#) на Atm(#i), если д — f2 и выполняется только одно из следующих условий: -
1) 7Г — (/,<?)- изоморфизм Atm(f/) на Atm(#i);
2) д - эпиморфизм полугруппы End Я на полугруппу EndЯl, / -эпиморфизм Н на Hi, удовлетворяющий условию ker/ = £ц и Я] -однореберный гиперграф, число вершин которого совпадает с числом компонент связности гиперграфа Я.
В разделе 3.5 изучается строение мономорфизмов универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами.
Автор выражает глубокую благодарность научному руководителю профессору Молчанову Владимиру Александровичу за постановку задач и поддержку в исследованиях.
Список литературы
1. Биркгоф Г., Барти Т. Современная прикладная алгебра. - М.: Мир, 1976.
2. Богомолов A.M., Салий В.Н. Алгебраические основы теории дискретных систем. - М.: Наука. Физматлит, 1997.
3. Бредихин Д.А. Инверсные полугруппы локальных автоморфизмов универсальных алгебр // Сибирск. матем. журнал, 1975. т.17, N3. С.490-507.
4. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. -М., Наука, 1980.
5. Зыков A.A. Гиперграфы // УМН, 1974. т.29, N6. С. 89-154.
6. Картези Ф. Введение в конечные геометрии: Пер. с англ.- М.: Наука. Главная редакция физико-математической литературы, 1980.
7. Кудрявцев В.Б., Алешин С.В., Подколзин A.C. Введение в теорию автоматов. - М.: Наука, 1985.
8. Ляпин Е.С. Полугруппы. - М.: Физматлит, 1960.
9. Молчанов A.B. Об определяемости гиперграфических автоматов их выходными функциями // Теоретические проблемы информатики и ее приложений. — Саратов, 1998. Вып.2. С.74-84.
10. Молчанов A.B. Полутруппы эндоморфизмов слабых р-гиперграфов // Известия вузов. Математика, 2000. N3(454). С.80-83.
11. Плоткин Б.И., Гринглаз Л.Я., Гварамия A.A. Элементы алгебраической теории автоматов. - М.:Высшая школа, 1994.
12. Улам С. Нерешенные математические задачи. - М.: Наука, 1964.
13. Eilenberg S. Automata, languages and machmes. Vol.В. - New York, San Francisco, London: Academic Press, 1976.
14. Jonsson B. Topics in universal algebra. Lecture Notes in Math. N250. -Berlin - Heidelberg - New York: Springer-Verlag, 1972.
15. Konig D. Theorie der endlichen und unendlichen Graphen, Leipzig, 1936.
16. Krasner M. Endotheorie de Galois abstraktion. Semin. Dubriel, Dubriel-Jacotin, Lesieur et Pisot. Fac. sei. Paris, 1968-1969(1970). V. 22, N 1. S. 6/01-6/19.
17. Molchanov V. A. Semigroups of mappings on graphs // Semigroup Forum 27, 1983. P.155-199.
ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ
Al. Хворостухина Е.В. О гомоморфизмах полугрупп эндоморфизмов гииерграфов //Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика, 2009. Т. 9, Вып. 3. С.70-75.
А2. Kbvorostukhina Е. On concrete characterization of universal hypergraphic automata // Journal of Mathematical Sciences. - New York: Springer New York, 2010. Vol. 164, N2. P.303-308.
A3. Хворостухина E.B. О конкретной характеризации универсальных гиперграфических автоматов // Международная алгебраическая конференция, посвященная 100-летию со дня рождения А.Г. Куроша. Тезисы докладов. - М.: Изд-во механико-математического факультета МГУ, 2008. С. 241-242.
A4. Хворостухина Е.В. Об определяемое™ гиперграфических автоматов полугруппами их входных сигналов // XV международная конференция "Проблемы теоретической кибернетики". Тезисы докладов.
- Казань: изд-во Казанского гос. ун-та, 2008. С.121.
А5. Хворостухина Е.В. О полугруппах эндоморфизмов гиперграфов // Современные проблемы дифференциальной геометрии и общей алгебры: Тезисы докл. Междунар. научн. конф., посвящ. 100-летию со дня рождения проф. В.В. Вагнера. - Саратов: Изд-во Сарат. ун-та, 2008. С.136-137.
А6. Хворостухина Е.В. О моделировании гиперграфических автоматов // Математические методы в технике и технологиях -ММТТ-21: сб.трудов XXI Международ, науч. конф.: в 10 т. - Саратов: Сарат.гос.техн.ун-т, 2008. Т.1. С.86-88.
А7. Хворостухина Е.В. Об автоморфизмах проективных плоскостей // Социально-экономическое развитие России: Проблемы, поиски, решения: сборник науч. трудов по итогам научно-иссяедоват. работы СГСЭУ в 2007 году. - Саратов: Сарат. гос. соц-экон. ун-т, 2008. 4.1. С.101-102.
А8. Хворостухина Е.В. О конкретной характеризации универсальных гиперграфических автоматов // Математика. Механика: Сб.науч. тр. -Саратов: Изд-во Сарат. ун-та, 2008. Вып. 10. С.151-154.
А9. Хворостухина Е.В. Об одном классе гиперграфических автоматов // Теоретические проблемы информатики и ее приложений: сб.науч.тр.
- Саратов: Изд-во Сарат. ун-та, 2008. Вып.8. С.112-118.
АЮ. Хворостухина Е.В. Построение плоскости. - М.: ВНТИЦ, 2008. -N 50200802489.
All. Хворостухина Е.В. О конкретной характеризации универсальных гиперграфических автоматов // Фундаментальная
и прикладная математика, 2008. Т.14. N7, С.223-231.
А12. Хворостухина Е.В. Об эпиморфизмах автоматов // Социально-экономическое развитие России: Проблемы, поиски, решения: Сборник научных трудов по итогам научно-исследовательской работы СГСЭУ в 2008 г.: в 2-х частях. - Саратов: Сарат. гос. соц-экон. ун-т, 2009.4.1. С.41.
А13. Хворостухина Е.В. Об относительно элементарной определимости класса гиперграфических автоматов в классе всех полугрупп // Международная научная конференция "Компьютерные науки и информационные технологии". - Саратов: изд-во Сарат, ун-та, 2009. С.210-212.
А14. Хворостухина Е.В. Об относительно элементарной определимости класса гиперграфов в классе всех полугрупп // Междунар. конференция "Мальцевские чтения", поев. 100-летию со дня рожд. А.И. Мальцева. Тезисы докладов. - Новосибирск, 2009. С.170.
А15. Хворостухина Е.В. О хопфовости полугрупп эндоморфизмов гиперграфов // Алгебра и ее приложения: труды Междун. алгебр, конф., посвящ. 80-летию со дня рождения А.И. Кострикина. - Нальчик: Каб,-Балк. ун-т, 2009. С.130-132.
А16. Хворостухина Е.В. Об эпиморфизмах гиперграфических автоматов // Математика. Механика: Сб. науч. тр. - Саратов: Изд-во Сарат. ун-та, 2009. Вып. И. С.82-84.
А17. Хворостухина Е.В. О мономорфизмах гиперграфических автоматов // Социально-экономическое развитие России: Проблемы, поиски, решения: Сборник научных трудов по итогам научно-исследовательской работы СГСЭУ в 2009 г.: в 2-х частях. - Саратов: Сарат. гос. соц-экон. ун-т, 2010. 4.1. С.119-120.
А18. Хворостухина Е.В. О мономорфизмах автоматов // Труды Математического центра имени Н. И. Лобачевского: материалы Международной научной конференции "Воображаемая логика"Н.А. Васильева и современные неклассические логики". -Казань: Казан, мат. об-во, 2010. Т.41. С.103-105.
Подписано в печать 19.01.2011г. Формат 60 х 84 1/16. Бумага типогр. N1. Печать RISO. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ {Ц .
410003, г. Саратов, ул. Радищева, 89. СГСЭУ.
Введение
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) описана взаимосвязь эпиморфизмов универсальных гиперграфических автоматов над эффективными гиперграфами с р—определимыми ребрами с морфизмами полугрупп входных сигналов этих автоматов.
Полученные результаты решают ряд принципиальных вопросов о взаимосвязи гиперграфических автоматов с их полугруппами входных сигналов, а также дают весьма эффективный инструмент для дальнейшего разностороннего исследования этой проблематики в алгебраической теории автоматов и для разнообразных приложений к комбинаторным исследованиям автоматов, изучению вопросов классификации автоматов средствами языка УИП и анализу проблем -разрешимости элементарных теорий классов автоматов.
Приведенные результаты могут быть использованы в алгебраической теории автоматов, теории гиперграфов и теории полугрупп.
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.
