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

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

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


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

Молчанов В. А., Хворостухина Е. В. Об элементарной определимости класса универсальных гиперграфических автоматов в классе полугрупп // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2022. Т. 22, вып. 3. С. 293-306. DOI: 10.18500/1816-9791-2022-22-3-293-306

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

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

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

Гиперграфическими автоматами называются автоматы, у которых множества состояний и выходных сигналов наделены структурами гиперграфов, сохраняющимися функциями переходов и выходными функциями. Универсальные притягивающие объекты в категории таких автоматов называются универсальными  гиперграфическими автоматами. Для таких автоматов  полугруппы входных сигналов являются производными алгебрами отображений, свойства которых взаимосвязаны со свойствами алгебраической структуры исходного автомата. Это позволяет изучать универсальные  гиперграфические автоматы с помощью исследования их полугрупп входных сигналов. Ранее авторами было доказано, что такие автоматы над гиперграфами из довольно широкого класса полностью (с точностью до изоморфизма) определяются своими полугруппами входных сигналов. В настоящей работе доказывается элементарная определимость класса таких автоматов в классе полугрупп. Основной результат статьи дает решение этой задачи для универсальных  гиперграфических автоматов над $p$-гиперграфами. Это достаточно широкий и весьма важный класс автоматов, так как он содержит, в частности, автоматы, у которых гиперграфы состояний и выходных сигналов являются плоскостями (например, проективными или аффинными). Полученные результаты показывают, что универсальный гиперграфический автомат над $p$-гиперграфами с точностью до изоморфизма представляется как алгебраическая система, построенная в полугруппе входных сигналов этого автомата с помощью канонических отношений этого автомата, которые  определяются формулами элементарной теории полугрупп. С помощью такого представления автоматов определяется эффективная синтаксическая трансформация формул  элементарной теории гиперграфических автоматов в формулы элементарной теории полугрупп, что позволяет всесторонне исследовать взаимосвязь элементарных свойств универсальных гиперграфических автоматов над $p$-гиперграфами и их полугрупп входных сигналов.

Список источников: 
  1. Плоткин Б. И., Гринглаз Л. Я., Гварамия А. А. Элементы алгебраической теории автоматов. Москва : Высшая школа, 1994. 192 c.
  2. Молчанов В. А., Хворостухина Е. В. Об абстрактной определяемой универсальности гиперграфических автоматов полугруппами входных сигналов // Чебышевский сборник. 2019. Т. 20, вып. 2 (70). С. 251–264. https://doi.org/10.22405/2226-8383-2019-20-2-251-264
  3. Khvorostukhina E. V., Molchanov V. A. Abstract characterization of input symbol semigroups of universal hypergraphic automata // Lobachevskii Journal of Mathematics. 2020. Vol. 41, № 2. P. 214–226. https://doi.org/10.1134/S1995080220020109
  4. Khvorostukhina E. V., Molchanov V. A. Universal hypergraphic automata representation by autonomous input symbols // Modeling and Analysis of Information Systems. 2018. Vol. 25, № 5 (77). P. 561–571 . https://doi.org/10.18255/1818-1015-2018-5-561-571
  5. Важенин Ю. М., Пинус А. Г. Элементарная классификация и разрешимость теорий производных структур // Успехи математических наук. 2005. Т. 60, № 3. C. 3–40. https://doi.org/10.4213/rm1428
  6. Пинус А. Г. Об элементарной эквивалентности производных структур свободных решеток // Известия высших учебных заведений. Математика. 2002. № 5. C. 44–47. EDN: HQUCWH
  7. Пинус А. Г. Об элементарной эквивалентности производных структур свободных полугрупп, унаров и групп // Алгебра и логика. 2004. Т. 43, № 6. C. 730–748. EDN: HRTFFV
  8. Пинус А. Г. Об элементарной эквивалентности решеток подалгебр и групп автоморфизмов свободных алгебр // Сибирский математический журнал. 2008. Т. 49, № 4. C. 865–869. EDN: IUFRIV
  9. Важенин Ю. М. Элементарные свойства полугрупп преобразований упорядоченных множеств // Алгебра и логика. 1970. Т. 9, № 3. С. 281–301.
  10. Важенин Ю. М. Об элементарной определяемости и элементарной характеризуемости классов рефлексивных графов // Известия высших учебных заведений. Математика. 1972. № 7. С. 3–11.
  11. Бунина Е. И., Михалeв А. В. Элементарная эквивалентность колец эндоморфизмов абелевых p-групп // Фундаментальная и прикладная математика. 2004. Т. 10, № 2. C. 135–224. EDN: HQLMNP
  12. Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. Москва : Наука, 1980. 416 c.
  13. Мальцев А. И. Алгебраические системы. Москва : Наука, 1970. 392 с.
  14. Lallement G. Semigroups and Combinatorial Applications. New York : Wiley, 1979. 376 p.
  15. Вагнер В. В. Теория отношений и алгебра частичных отображений // Теория полугрупп и ее приложения : сб. ст. Саратов : Изд-во Саратовского ун-та, 1965. Вып. 1. С. 3–178.
  16. Bretto A. Hypergraph Theory. An Introduction. Cham : Springer, 2013. 119 p. https://doi.org/10.1007/978-3-319-00080-0
  17. Картеси Ф. Введение в конечные геометрии. Москва : Наука, 1980. 320 c.
Поступила в редакцию: 
14.01.2022
Принята к публикации: 
28.01.2022
Опубликована: 
31.08.2022