matatecsМатематика и теоретические компьютерные наукиMathematics and Theoretical Computer Science2949-3919Казанский (Приволжский) федеральный университет10.26907/2949-3919.2024.4.103-123matatecs-65Research ArticleСТАТЬИОтносительно элементарная определимость класса универсальных частичных графовых полуавтоматов в классе полугруппRelatively elementary definability of the class of universal partial graphic semiautomata in the class of semigroupsМолчановВ. А.MolchanovV. A.

Владимир Александрович Молчанов

ул. Астраханская, д. 83, г. Саратов, 410012

Vladimir Aleksandrovich Molchanov

83 Astrakhanskaya str., Saratov 410012

v.molchanov@inbox.ruФарахутдиновР. А.FarakhutdinovR. A.

Ренат Абуханович Фарахутдинов

ул. Астраханская, д. 83, г. Саратов, 410012

Renat Abukhanovich Farakhutdinov

83 Astrakhanskaya str., Saratov 410012

renatfara@mail.ruСаратовский государственный университет им. Н.Г. ЧернышевскогоРоссияSaratov State UniversityRussian FederationСаратовский государственный университет им. Н.Г.ЧернышевскогоРоссияSaratov State UniversityRussian Federation20242401202524103123Copyright © Молчанов В.А., Фарахутдинов Р.А., 20252025Молчанов В.А., Фарахутдинов Р.А.Molchanov V.A., Farakhutdinov R.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matatecs.elpub.ru/jour/article/view/65

Работа посвящена алгебраической теории структуризированных автоматов. Рассматриваются полугрупповые автоматы без выходных сигналов над графами, которые называются графовыми полуавтоматами. Изучаются частичные графовые полуавтоматы, каждый входной сигнал которых является частичным эндоморфизмом графа состояний. В категории частичных графовых полуавтоматов над графом G = (X, ρ) особое внимание уделяется полуавтомату PAtm(G) = (G, PEnd(G),⋆) с полугруппой PEnd(G) всех частичных эндоморфизмов графа G, так как он является универсально притягивающим объектом в данной категории и называется универсальным частичным графовым полуавтоматом. Основной результат работы состоит в доказательстве относительно элементарной определимости класса универсальных частичных графовых полуавтоматов над нетривиальными рефлексивными графами в классе полугрупп и ее приложений.

The work is devoted to the algebraic theory of structured automata. We consider semigroup automata without output signals over graphs, which are called graphic semiautomata. We study partial graphic semiautomata, each input signal of which is a partial endomorphism of the state graph. In the category of partial graphic semiautomata over the graph G = (X, ρ), special attention is paid to the semiautomaton PAtm(G) = (G, PEnd(G),⋆) with semigroup PEnd(G) of all partial endomorphisms of the graph G, since it is a universally attracting object in this category and is called a universal partial graphic semiautomaton. The main result of the work is the proof of the relatively elementary definability of the class of universal partial graphic semiautomata over nontrivial reflexive graphs in the class of semigroups, and applications of got relatively elementary definability.

полуавтоматграфчастичный эндоморфизмотносительно элементарная определимостьsemiautomatongraphpartial endomorphismrelatively elementary definabilityReferencesБ.И. Плоткин, Л.Я. Гринглаз, А.А. Гварамия, Элементы алгебраической теории автоматов, Высш. шк., М., 1994.B.I. Plotkin, L.Ja. Greenglaz, A.A. Gvaramija, Elements of algebraic theory of automata, Vysshaya shkola, M., 1994 [in Russian].Р. Лидл, Г. Пильц, Прикладная абстрактная алгебра, Изд-во Урал. ун-та, Екатеринбург, 1996.R. Lidl, G. Pilz, Applied abstract algebra, Springer-Verlag, New York, 1998. DOI: https://doi.org/10.1007/978-1-4757-2941-2С. Улам, Нерешенные математические задачи, Наука, М., 1964.S. Ulam, A collection of mathematical problems, Interscience Publ., New York, 1960.Б.И. Плоткин, Группы автоморфизмов алгебраических систем, Наука, М., 1966.B.I. Plotkin, Groups of automorphisms of algebraic systems, Wolters-Noordhoff Publ., Groningen, 1972.А.Г. Пинус, Об элементарной эквивалентности производных структур свободных полугрупп, унаров и групп, Алгебра и логика 43 (6), 730–748 (2004). URL: https://www.mathnet.ru/rus/al107A.G. Pinus, Elementary equivalence of derived structures of free semigroups, unars, and groups, Algebra Logic 43 (6), 408–417 (2004). DOI: https://doi.org/10.1023/B:ALLO.0000048829.60182.48А.Г. Пинус, Об элементарной эквивалентности производных структур свободных решеток, Изв. вузов. Матем. (5), 44–47 (2002). URL: https://www.mathnet.ru/rus/ivm1014A.G. Pinus, Elementary equivalence of derived structures of free lattices, Russ. Math. 46 (5), 42–45 (2002).Ю.М. Важенин, Элементарные свойства полугрупп преобразований упорядоченных множеств, Алгебра и логика 9 (3), 281–301 (1970). URL: https://www.mathnet.ru/rus/al1245Yu.M. Vazhenin, Elementary properties of semigroups of transformations of ordered sets, Algebra Logic 9 (3), 281–301 (1970) [in Russian]. URL: https://www.mathnet.ru/rus/al1245Ю.М. Важенин, Об элементарной определяемости и элементарной характеризуемости классов рефлексивных графов, Изв. вузов. Матем. (7), 3–11 (1972). URL: https://www.mathnet.ru/rus/ivm4076Yu.M. Vazhenin, The elementary definability and elementary characterizability of classes of reflexive graphs, Izv. Vyssh. Uchebn. Zaved. Mat. (7), 3–11 (1972) [in Russian]. URL: https://www.mathnet.ru/rus/ivm4076Л.М. Глускин, Полугруппы и кольца эндоморфизмов линейных пространств, Изв. АН СССР. Сер. матем. 23 (6), 841–870 (1959). URL: https://www.mathnet.ru/rus/im3817L.M. Gluskin, Semigroups and endomorphism rings of linear spaces, Izv. Akad. Nauk SSSR Ser. Mat. 23 (6), 841–870 (1959) [in Russian]. URL: https://www.mathnet.ru/rus/im3817Л.М. Глускин, Полугруппы изотонных преобразований, УМН 16 (5), 157–162 (1961). URL: https://www.mathnet.ru/rus/rm6671L.M. Gluskin, Semigroups of isotone transformations, Uspekhi Mat. Nauk 16 (5), 157–162 (1961) [in Russian]. URL: https://www.mathnet.ru/rus/rm6671В.Т. Марков, А.В. Михалёв, Л.А. Скорняков, А.А. Туганбаев, Кольца эндоморфизмов модулей и структуры подмодулей, Итоги науки и техн. Сер. Алгебра. Топол. Геом. 21, 183–254 (1983). URL: https://www.mathnet.ru/rus/inta105V.T. Markov, A.V. Mikhalev, L.A. Skornyakov, A.A. Tuganbaev, Endomorphism rings of modules, and lattices of submodules, J. Soviet Math. 31 (3), 3005–3051 (1985). DOI: https://doi.org/10.1007/BF02106808Ю.Л. Ершов, Проблемы разрешимости и конструктивные модели, Наука, М., 1980.Yu.L. Ershov, Decidability problems and constructive models, Nauka, M., 1980 [in 1109 Russian].Р.А. Фарахутдинов, Относительно элементарная определимость класса универсальных графовых полуавтоматов в классе полугрупп, Изв. вузов. Матем. (1), 74–84 (2022). DOI: https://doi.org/10.26907/0021-3446-2022-1-74-84R.A. Farakhutdinov, Relatively elementary definability of the class of universal graphic semiautomata in the class of semigroups, Russ. Math. 66 (1), 62–70 (2022). DOI: https://doi.org/10.3103/S1066369X22010029А.И. Мальцев, Алгебраические системы, Наука, М., 1970.A.I. Mal’cev, Algebraic Systems, Springer-Verlag, New York–Heidelberg, 1973. DOI: https://doi.org/10.1007/978-3-642-65374-2Ф. Харари, Теория графов, Мир, М., 1973.F. Harary, Graph theory, Addison-Wesley Publ., 1969. DOI: https://doi.org/10.1201/9780429493768А. Клиффорд, Г. Престон, Алгебраическая теория полугрупп, Мир, М., 1972.A.H. Clifford, G.B. Preston, The algebraic theory of semigroups, AMS, New York, 1967.В.В. Вагнер, Полугруппы частичных преобразований с симметричным отношением транзитивности, Изв. вузов. Матем. (1), 81–88 (1957). URL: https://www.mathnet.ru/rus/ivm3022V.V. Vagner, Semigroups of partial transformations with a symmetric transitivity relation, Izv. Vyssh. Uchebn. Zaved. Mat. (1), 81–88 (1957) [in Russian]. URL: https://www.mathnet.ru/rus/ivm3022А. Робинсон, Введение в теорию моделей и метаматематику алгебры, Наука. Физматлит, М., 1967.A. Robinson, Introduction to model theory and to the metamathematics of algebra, North-Holland Publ., 1965.Ю.Л. Ершов, И.А. Лавров, А.Д. Тайманов, М.А. Тайцлин, Элементарные теории, УМН 20 (4), 37–108 (1965). URL: https://www.mathnet.ru/rus/rm6048Yu.L. Ershov, I.A. Lavrov, A.D. Taimanov, M.A. Taitslin, Elementary theories, Russ. Math. Surv. 20 (4), 35–105 (1965). DOI: https://doi.org/10.1070/RM1965v020n04ABEH001188

The authors declare that there are no conflicts of interest present.