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

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

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


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

Фарахутдинов Р. А. О конкретной характеризации универсальных графовых полуавтоматов // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2022. Т. 22, вып. 4. С. 458-467. DOI: 10.18500/1816-9791-2022-22-4-458-467

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
30.11.2022
Полный текст:
(downloads: 146)
Язык публикации: 
русский
Рубрика: 
Тип статьи: 
Научная статья
УДК: 
519.713.2
EDN: 
PKWNTS

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

Авторы: 
Фарахутдинов Ренат Абуханович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

Теория автоматов является одним из разделов математической кибернетики, в котором изучаются устройства преобразования информации, используемые во многих прикладных задачах. В данной работе мы изучаем автоматы без выходных сигналов и называем их полуавтоматами. В зависимости от исследуемых задач рассматриваются полуавтоматы, у которых множества состояний наделены дополнительной математической структурой, согласованной с функцией переходов полуавтомата. Мы исследуем полуавтоматы над графами (так называемые графовые полуавтоматы), множество состояний которых наделено математической структурой графа. Универсальный графовый полуавтомат $\rm{Atm}(G)$ — это универсально притягивающий объект в категории полуавтоматов, у которых множество состояний наделено структурой графа $G$, сохраняющейся функцией переходов полуавтомата. Полугруппа входных сигналов такого полуавтомата имеет вид $S(G)=\rm{End}\ G$. Она может рассматриваться как производная алгебраическая система математического объекта $\rm{Atm}(G)$, которая содержит полезную информацию об исходном объекте. Свойства такой полугруппы взаимосвязаны со свойствами алгебраической структуры полуавтомата, это означает, что универсальные графовые полуавтоматы можно изучать путем исследования их полугрупп входных сигналов. Для таких полугрупп представляет интерес проблема конкретной характеризации универсальных графовых полуавтоматов: при каких условиях на множестве состояний $X$ полуавтомата $A=(X,S,\delta)$ возможно задать бинарное отношение $\rho$, такое, что для графа $G=(X,\rho)$ будет выполняться равенство $A=\rm{Atm}(G)$. В данной работе эта проблема решается для графовых полуавтоматов над рефлексивными квазибесконтурными графами.

Список источников: 
  1. Плоткин Б. И. Группы автоморфизмов алгебраических систем. Москва : Наука, 1966. 604 с.
  2. Пинус А. Г. Об элементарной эквивалентности производных структур свободных полугрупп, унаров и групп // Алгебра и логика. 2004. Т. 43, № 6. С. 730–748. EDN: HRTFFV
  3. Пинус А. Г. Об элементарной эквивалентности производных структур свободных решеток // Известия высших учебных заведений. Математика. 2002. № 5. С. 44–47. EDN: HQUCWH
  4. Важенин Ю. М. Элементарные свойства полугрупп преобразований упорядоченных множеств // Алгебра и логика. 1970. Т. 9, № 3. С. 281–301.
  5. Важенин Ю. М. Об элементарной определяемости и элементарной характеризуемости классов рефлексивных графов // Известия высших учебных заведений. Математика. 1972. № 7. С. 3–11.
  6. Глускин Л. М. Полугруппы и кольца эндоморфизмов линейных пространств // Известия Академии наук СССР. Серия математическая. 1959. Т. 23, вып. 6. С. 841–870.
  7. Глускин Л. М. Полугруппы изотонных преобразований // Успехи математических наук. 1961. Т. 16, вып. 5 (101). С. 157–162.
  8. Марков В. Т., Михалeв А. В., Скорняков Л. А., Туганбаев А. А. Кольца эндоморфизмов модулей и структуры подмодулей // Итоги науки и техники. Серия: Алгебра. Топология. Геометрия. Москва : ВИНИТИ, 1983. Т. 21. С. 183–254.
  9. Улам С. Нерешенные математические задачи. Москва : Наука, 1964. 168 с.
  10. Плоткин Б. И., Гринглаз Л. Я., Гварамия А. А. Элементы алгебраической теории автоматов. Москва : Высшая школа, 1994. 191 с.
  11. Лидл Р., Пильц Г. Прикладная абстрактная алгебра : пер. с англ. Екатеринбург : Изд-во Уральского ун-та, 1996. 744 с.
  12. Мальцевские чтения : тезисы докладов Международной конференции. Новосибирск, 2020. URL: http://www.math.nsc.ru/conference/malmeet/20/maltsev20.pdf (дата обращения: 15.01.2022).
  13. Материалы Международного молодежного научного форума «ЛОМОНОСОВ-2020» [Электронный ресурс] / отв. ред. И. А. Алешковский, А. В. Андриянов, Е. А. Антипов. Электрон. текстовые дан. (1500 Мб.). Москва : МАКС Пресс, 2020. URL: https://lomonosov-msu.ru/archive/Lomonosov_2020/index.htm (дата обращения: 15.01.2022).
  14. Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. Москва : Наука. Физматлит, 1997. 368 с.
  15. Харари Ф. Теория графов. Москва : Мир, 1973. 300 с.
  16. Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. Москва : Наука. Физматлит, 1980. 416 с. 
Поступила в редакцию: 
16.01.2022
Принята к публикации: 
17.02.2022
Опубликована: 
30.11.2022