Относительно элементарная определимость класса универсальных частичных графовых полуавтоматов в классе полугрупп
https://doi.org/10.26907/2949-3919.2024.4.103-123
Аннотация
Работа посвящена алгебраической теории структуризированных автоматов. Рассматриваются полугрупповые автоматы без выходных сигналов над графами, которые называются графовыми полуавтоматами. Изучаются частичные графовые полуавтоматы, каждый входной сигнал которых является частичным эндоморфизмом графа состояний. В категории частичных графовых полуавтоматов над графом G = (X, ρ) особое внимание уделяется полуавтомату PAtm(G) = (G, PEnd(G),⋆) с полугруппой PEnd(G) всех частичных эндоморфизмов графа G, так как он является универсально притягивающим объектом в данной категории и называется универсальным частичным графовым полуавтоматом. Основной результат работы состоит в доказательстве относительно элементарной определимости класса универсальных частичных графовых полуавтоматов над нетривиальными рефлексивными графами в классе полугрупп и ее приложений.
Об авторах
В. А. Молчанов
Саратовский государственный университет им. Н.Г. Чернышевского
Россия
Россия
Владимир Александрович Молчанов
ул. Астраханская, д. 83, г. Саратов, 410012
Р. А. Фарахутдинов
Саратовский государственный университет им. Н.Г.Чернышевского
Россия
Россия
Ренат Абуханович Фарахутдинов
ул. Астраханская, д. 83, г. Саратов, 410012
Список литературы
1. Б.И. Плоткин, Л.Я. Гринглаз, А.А. Гварамия, Элементы алгебраической теории автоматов, Высш. шк., М., 1994.
2. Р. Лидл, Г. Пильц, Прикладная абстрактная алгебра, Изд-во Урал. ун-та, Екатеринбург, 1996.
3. С. Улам, Нерешенные математические задачи, Наука, М., 1964.
4. Б.И. Плоткин, Группы автоморфизмов алгебраических систем, Наука, М., 1966.
5. А.Г. Пинус, Об элементарной эквивалентности производных структур свободных полугрупп, унаров и групп, Алгебра и логика 43 (6), 730–748 (2004). URL: https://www.mathnet.ru/rus/al107
6. А.Г. Пинус, Об элементарной эквивалентности производных структур свободных решеток, Изв. вузов. Матем. (5), 44–47 (2002). URL: https://www.mathnet.ru/rus/ivm1014
7. Ю.М. Важенин, Элементарные свойства полугрупп преобразований упорядоченных множеств, Алгебра и логика 9 (3), 281–301 (1970). URL: https://www.mathnet.ru/rus/al1245
8. Ю.М. Важенин, Об элементарной определяемости и элементарной характеризуемости классов рефлексивных графов, Изв. вузов. Матем. (7), 3–11 (1972). URL: https://www.mathnet.ru/rus/ivm4076
9. Л.М. Глускин, Полугруппы и кольца эндоморфизмов линейных пространств, Изв. АН СССР. Сер. матем. 23 (6), 841–870 (1959). URL: https://www.mathnet.ru/rus/im3817
10. Л.М. Глускин, Полугруппы изотонных преобразований, УМН 16 (5), 157–162 (1961). URL: https://www.mathnet.ru/rus/rm6671
11. В.Т. Марков, А.В. Михалёв, Л.А. Скорняков, А.А. Туганбаев, Кольца эндоморфизмов модулей и структуры подмодулей, Итоги науки и техн. Сер. Алгебра. Топол. Геом. 21, 183–254 (1983). URL: https://www.mathnet.ru/rus/inta105
12. Ю.Л. Ершов, Проблемы разрешимости и конструктивные модели, Наука, М., 1980.
13. Р.А. Фарахутдинов, Относительно элементарная определимость класса универсальных графовых полуавтоматов в классе полугрупп, Изв. вузов. Матем. (1), 74–84 (2022). DOI: https://doi.org/10.26907/0021-3446-2022-1-74-84
14. А.И. Мальцев, Алгебраические системы, Наука, М., 1970.
15. Ф. Харари, Теория графов, Мир, М., 1973.
16. А. Клиффорд, Г. Престон, Алгебраическая теория полугрупп, Мир, М., 1972.
17. В.В. Вагнер, Полугруппы частичных преобразований с симметричным отношением транзитивности, Изв. вузов. Матем. (1), 81–88 (1957). URL: https://www.mathnet.ru/rus/ivm3022
18. А. Робинсон, Введение в теорию моделей и метаматематику алгебры, Наука. Физматлит, М., 1967.
19. Ю.Л. Ершов, И.А. Лавров, А.Д. Тайманов, М.А. Тайцлин, Элементарные теории, УМН 20 (4), 37–108 (1965). URL: https://www.mathnet.ru/rus/rm6048
Рецензия
Для цитирования:
Молчанов В.А., Фарахутдинов Р.А. Относительно элементарная определимость класса универсальных частичных графовых полуавтоматов в классе полугрупп. Математика и теоретические компьютерные науки. 2024;2(4):103-123. https://doi.org/10.26907/2949-3919.2024.4.103-123
For citation:
Molchanov V.A., Farakhutdinov R.A. Relatively elementary definability of the class of universal partial graphic semiautomata in the class of semigroups. Mathematics and Theoretical Computer Science. 2024;2(4):103-123. (In Russ.) https://doi.org/10.26907/2949-3919.2024.4.103-123
Просмотров:
56
Послать статью по эл. почте 