Для цитирования:
Молчанов В. А., Хворостухина Е. В. О задаче абстрактной характеризации универсальных гиперграфических автоматов // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2017. Т. 17, вып. 2. С. 148-159. DOI: 10.18500/1816-9791-2017-17-2-148-159, EDN: ZEVWZR
О задаче абстрактной характеризации универсальных гиперграфических автоматов
Гиперграфическими автоматами называются автоматы, у которых множества состояний и выходных символов наделены структурами гиперграфов, сохраняющимися функциями переходов и выходными функциями. Универсальные притягивающие объекты в категории таких автоматов представляются автоматами Atm (H1,H2) с гиперграфом состояний H1, гиперграфом выходных символов H2 и полугруппой входных символов S = End H1 × Hom(H1,H2), которые называются универсальными гиперграфическими автоматами. Для такого автомата Atm (H1,H2) полугруппа входных символов S является производной алгеброй отображений, свойства которой взаимосвязаны со свойствами алгебраической структуры данного автомата. Это позволяет изучать универсальные гиперграфические автоматы с помощью исследования их полугрупп входных символов. В настоящей работе исследуется проблема абстрактной характеризации универсальных гиперграфических автоматов, суть которой заключается в нахождении условий изоморфности произвольного автомата некоторому универсальному гиперграфическому автомату. Основной результат работы дает решение этой задачи для универсальных гиперграфических автоматов над эффективными гиперграфами с p-определимыми ребрами. Это достаточно широкий и весьма важный класс автоматов, так как он содержит, в частности, автоматы, у которых гиперграфы состояний и выходных символов являются плоскостями (например, проективными или аффинными) или разбиениями на классы нетривиальных эквивалентностей. Для решения основной задачи работы показано, что алгебраическая структура эффективных гиперграфов с p-определимыми ребрами полностью определяется отношением (p + 1)-ограниченности его вершин и для универсальных гиперграфических автоматов над такими гиперграфами алгебраическая структура гиперграфов состояний и выходных символов полностью определяется каноническими отношениями полугруппы входных символов таких автоматов.
- Плоткин Б. И., Гринглаз Л. Я., Гварамия А. А. Элементы алгебраической теории автоматов. М. : Высш. шк., 1994. 192 с.
- Улам С. Нерешенные математические задачи. М. : Наука, 1964. 168 с.
- Jonsson B. Topics in universal algebra. Lecture Notes in Math. Berlin ; Heidelberg ; N.Y. : Springer-Verlag, 1972. 220 p.
- Молчанов В. А., Хворостухина Е. В. О задаче конкретной характеризации универсальных гиперграфических автоматов // Компьютерные науки и информационные технологии : материалы междунар. науч. конф. Саратов : ИЦ Наука, 2016. С. 284–285.
- Bretto A. Hypergraph theory. An Introduction. Cham ; Heidelberg ; N.Y. ; Dordrecht ; London : Springer, 2013. 133 p. DOI: https://doi.org/10.1007/978-3-319-00080-0.
- Хартсхорн Р. Основы проективной геометрии. М. : Мир, 1970. 161 с.
- Молчанов А. В. Полугруппы эндоморфизмов cлабых p-гиперграфов // Изв. вузов. Матем. 2000. № 3. С. 80–83.
- Молчанов А. В. Об определяемости гиперграфических автоматов их выходными функциями // Теоретические проблемы информатики и ее приложений. 1998. Вып. 2. С. 74–84.
- 954 просмотра