Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Молчанов В. А., Хворостухина Е. В. О задаче абстрактной характеризации универсальных гиперграфических автоматов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2017. Т. 17, вып. 2. С. 148-159. DOI: 10.18500/1816-9791-2017-17-2-148-159

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
22.05.2017
Полный текст:
(downloads: 46)
Язык публикации: 
русский
Рубрика: 
УДК: 
519.7

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

Авторы: 
Молчанов Владимир Александрович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Хворостухина Екатерина Владимировна, Саратовский государственный технический университет имени Гагарина Ю.А.
Аннотация: 

Гиперграфическими автоматами называются автоматы, у которых множества состояний и выходных символов наделены структурами гиперграфов, сохраняющимися функциями переходов и выходными функциями. Универсальные притягивающие объекты в категории таких автоматов представляются автоматами Atm (H1,H2) с гиперграфом состояний H1, гиперграфом выходных символов H2 и полугруппой входных символов S = End H1 × Hom(H1,H2), которые называются универсальными гиперграфическими автоматами. Для такого автомата Atm (H1,H2) полугруппа входных символов S является производной алгеброй отображений, свойства которой взаимосвязаны со свойствами алгебраической структуры данного автомата. Это позволяет изучать универсальные гиперграфические автоматы с помощью исследования их полугрупп входных символов. В настоящей работе исследуется проблема абстрактной характеризации универсальных гиперграфических автоматов, суть которой заключается в нахождении условий изоморфности произвольного автомата некоторому универсальному гиперграфическому автомату. Основной результат работы дает решение этой задачи для универсальных гиперграфических автоматов над эффективными гиперграфами с p-определимыми ребрами. Это достаточно широкий и весьма важный класс автоматов, так как он содержит, в частности, автоматы, у которых гиперграфы состояний и выходных символов являются плоскостями (например, проективными или аффинными) или разбиениями на классы нетривиальных эквивалентностей. Для решения основной задачи работы показано, что алгебраическая структура эффективных гиперграфов с p-определимыми ребрами полностью определяется отношением (p + 1)-ограниченности его вершин и для универсальных гиперграфических автоматов над такими гиперграфами алгебраическая структура гиперграфов состояний и выходных символов полностью определяется каноническими отношениями полугруппы входных символов таких автоматов.

Список источников: 

 

  1. Плоткин Б. И., Гринглаз Л. Я., Гварамия А. А. Элементы алгебраической теории автоматов. М. : Высш. шк., 1994. 192 с.
  2. Улам С. Нерешенные математические задачи. М. : Наука, 1964. 168 с.
  3. Jonsson B. Topics in universal algebra. Lecture Notes in Math. Berlin ; Heidelberg ; N.Y. : Springer-Verlag, 1972. 220 p.
  4. Молчанов В. А., Хворостухина Е. В. О задаче конкретной характеризации универсальных гиперграфических автоматов // Компьютерные науки и информационные технологии : материалы междунар. науч. конф. Саратов : ИЦ Наука, 2016. С. 284–285.
  5. 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.
  6. Хартсхорн Р. Основы проективной геометрии. М. : Мир, 1970. 161 с.
  7. Молчанов А. В. Полугруппы эндоморфизмов cлабых p-гиперграфов // Изв. вузов. Матем. 2000. № 3. С. 80–83.
  8. Молчанов А. В. Об определяемости гиперграфических автоматов их выходными функциями // Теоретические проблемы информатики и ее приложений. 1998. Вып. 2. С. 74–84.