О проблеме абстрактной характеризации универсальных графовых автоматов
https://doi.org/10.22405/2226-8383-2024-25-1-116-126
Аннотация
Данная работа посвящена алгебраической теории автоматов, являющейся одним из разделов математической кибернетики, в котором изучаются устройства преобразования информации, возникающие во многих прикладных задачах. В зависимости от исследуемых задач рассматриваются автоматы, у которых основные множества наделены дополнительными математическими структурами, согласованными с функциями автомата. В настоящей работе исследуются автоматы над графами — графовые автоматы, множество состояний и множество выходных сигналов которых наделены математическими структурами графов. Для графов 𝐺 и 𝐻 универсальный графовый автомат Atm(𝐺,𝐻) является универсально притягивающим объектом в категории графовых автоматов. Полугруппа вход-
ных сигналов такого автомата имеет вид 𝑆 = End 𝐺 × Hom(𝐺,𝐻). Естественно возникает интерес к исследованию вопроса абстрактной характеризации универсальных графовых автоматов: при каких условиях абстрактный автомат 𝐴 будет изоморфен универсальному графовому автомату Atm(𝐺,𝐻) над графами 𝐺 из класса K_1, 𝐻 из класса K_2? Целью работы является исследование вопроса элементарной аксиоматизации некоторых классов
графовых автоматов. Доказана невозможность элементарной аксиоматизации средствами языка узкого исчисления предикатов некоторых широких классов таких автоматов над рефлексивными графами.
Об авторе
Ренат Абуханович Фарахутдинов
Саратовский государственный университет им. Н.Г. Чернышевского
Россия
Россия
аспирант
Список литературы
1. Плоткин Б. И., Гринглаз Л. Я., Гварамия А. А. Элементы алгебраической теории автоматов. М.: Высш. шк., 1994. 191 с.
2. Плоткин Б. И. Группы автоморфизмов алгебраических систем. М.: Наука, 1966. 604 с.
3. Пинус А. Г. Об элементарной эквивалентности производных структур свободных полугрупп, унаров и групп // Алгебра и логика. 2004. Т. 43, №6. С. 730–748.
4. Пинус А. Г. Об элементарной эквивалентности производных структур свободных решеток // Изв. вузов. Матем. 2002. №5. С. 44–47.
5. Глускин Л. М. Полугруппы и кольца эндоморфизмов линейных пространств // Изв. АН СССР. Сер. мат. 1959. Т. 23. С. 841–870.
6. Глускин Л. М. Полугруппы изотонных преобразований // УМН. 1961. Т. 16, №5. С. 157–162.
7. Важенин Ю.М. Элементарные свойства полугрупп преобразований упорядоченных множеств // Алгебра и логика. 1970. Т. 9, №3. С. 281–301.
8. Важенин Ю.М. Об элементарной определяемости и элементарной характеризуемости классов рефлексивных графов // Изв. вузов. Матем. 1972. №7. С. 3–11.
9. Михалeв А. В. Кольца эндоморфизмов модулей и структуры подмодулей // Итоги науки и техн. Сер. Алгебра. Топол. Геом. 1974. Т. 12. С. 51–76.
10. Улам С. Нерешенные математические задачи. М.: Наука, 1964. 168 с.
11. Jonsson B. Topics in Universal Algebras // Lecture Notes in Math. Springer-Verlag, 1972. Vol. 250. P. 230.
12. Харари Ф. Теория графов. М.: Мир, 1973. 300 с.
13. Мальцев А. И. Алгебраические системы. М.: Наука. Физматлит, 1970. 392 с.
14. Акимова С. А. Абстрактная характеристика полугруппы эндоморфизмов упорядоченного множества // Математика. Механика: cб. науч. тр. Саратов : Изд-во Сарат. ун-та. 2004. №6. С. 3–5.
15. Фарахутдинов Р. А. Относительно элементарная определимость класса универсальных графовых полуавтоматов в классе полугрупп // Изв. вузов. Матем. 2022. №1. С. 74–84.
16. Кейслер Г., Чен Ч. Ч. Теория моделей. М.: Мир, 1977. 616 с.
17. Molchanov V. A., Farakhutdinov R. A. On Concrete Characterization of Universal Graphic Automata // Lobachevskii Journal of Mathematics. 2022. Vol. 43, №3. P. 664–671.
18. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970. 416 с.
Рецензия
Для цитирования:
Фарахутдинов Р.А. О проблеме абстрактной характеризации универсальных графовых автоматов. Чебышевский сборник. 2024;25(1):116-126. https://doi.org/10.22405/2226-8383-2024-25-1-116-126
For citation:
Farakhutdinov R.A. On the problem of abstract characterization of universal graphic automata. Chebyshevskii Sbornik. 2024;25(1):116-126. (In Russ.) https://doi.org/10.22405/2226-8383-2024-25-1-116-126
Просмотров:
265
Послать статью по эл. почте 