chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2024-25-1-116-126cheb-1680Research ArticleСтатьиArticleО проблеме абстрактной характеризации универсальных графовых автоматовOn the problem of abstract characterization of universal graphic automataФарахутдиновРенат АбухановичFarakhutdinovRenat Abukhanovich

аспирант

postgraduate student

renatfara@mail.ruСаратовский государственный университет им. Н.Г. ЧернышевскогоРоссияSaratov State UniversityRussian Federation202424042024251116126Copyright © Фарахутдинов Р.А., 20242024Фарахутдинов Р.А.Farakhutdinov R.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/1680

Данная работа посвящена алгебраической теории автоматов, являющейся одним из разделов математической кибернетики, в котором изучаются устройства преобразования информации, возникающие во многих прикладных задачах. В зависимости от исследуемых задач рассматриваются автоматы, у которых основные множества наделены дополнительными математическими структурами, согласованными с функциями автомата. В настоящей работе исследуются автоматы над графами — графовые автоматы, множество состояний и множество выходных сигналов которых наделены математическими структурами графов. Для графов 𝐺 и 𝐻 универсальный графовый автомат Atm(𝐺,𝐻) является универсально притягивающим объектом в категории графовых автоматов. Полугруппа вход-ных сигналов такого автомата имеет вид 𝑆 = End 𝐺 × Hom(𝐺,𝐻). Естественно возникает интерес к исследованию вопроса абстрактной характеризации универсальных графовых автоматов: при каких условиях абстрактный автомат 𝐴 будет изоморфен универсальному графовому автомату Atm(𝐺,𝐻) над графами 𝐺 из класса K_1, 𝐻 из класса K_2? Целью работы является исследование вопроса элементарной аксиоматизации некоторых классовграфовых автоматов. Доказана невозможность элементарной аксиоматизации средствами языка узкого исчисления предикатов некоторых широких классов таких автоматов над рефлексивными графами.

This work is devoted to the algebraic theory of automata, which is one of the branches of mathematical cybernetics, which studies information transformation devices that arise in many applied problems. Depending on a specific problem, automata are considered, in which the main sets are equipped with additional mathematical structures consistent with the functions of an automaton. In this work, we study automata over graphs — graphic automata, that is, automata in which the set of states and the set of output signals are equipped with the mathematical structure of graphs. For graphs 𝐺 and 𝐻 universal graphic automaton Atm(𝐺,𝐻) is a universally attracting object in the category of semigroup automata. The input signalsemigroup of such automaton is 𝑆 = End 𝐺×Hom(𝐺,𝐻). Naturally, interest arises in studying the question of abstract characterization of universal graph automata: under what conditions will the abstract automaton 𝐴 be isomorphic to the universal graph automaton Atm(𝐺,𝐻) over graphs 𝐺 from the class K_1, 𝐻 from class K_2? The purpose of the work is to study the issue of elementary axiomatization of some classes of graphic automata. The impossibility of elementaryaxiomatization by means of the language of restricted predicate calculus of some wide classes of such automata over reflexive graphs is proved.

автоматполугруппаграфабстрактная характеризацияаксиоматизация.automatonsemigroupgraphabstract characterizationaxiomatization.ReferencesПлоткин Б. И., Гринглаз Л. Я., Гварамия А. А. Элементы алгебраической теории автоматов. М.: Высш. шк., 1994. 191 с.Plotkin, B. I., Greenglaz, L. Ja. & Gvaramija, A. A., 1994, “Elements of algebraic theory of automata”, Vyshaja Shkola, Moscow, 191 p. (In Russ.)Плоткин Б. И. Группы автоморфизмов алгебраических систем. М.: Наука, 1966. 604 с.Plotkin, B. I., 1966, “Groups of automorphisms of algebraic systems”, Nauka, Moscow, 604 p. (In Russ.)Пинус А. Г. Об элементарной эквивалентности производных структур свободных полугрупп, унаров и групп // Алгебра и логика. 2004. Т. 43, №6. С. 730–748.Pinus, A. G., 2004, “Elementary equivalence of derived structures of free semigroups, unars, and groups”, Algebra and logic, vol. 43, no. 6, pp. 408–417 (In Russ.)Пинус А. Г. Об элементарной эквивалентности производных структур свободных решеток // Изв. вузов. Матем. 2002. №5. С. 44–47.Pinus, A.G., 2002, “Elementary equivalence of derived structures of free lattices”, Izv. Vyssh. Uchebn. Zaved. Mat., vol. 5, pp. 44–47 (In Russ.)Глускин Л. М. Полугруппы и кольца эндоморфизмов линейных пространств // Изв. АН СССР. Сер. мат. 1959. Т. 23. С. 841–870.Gluskin, L. M., 1961, “Semigroups and endomorphism rings of linear spaces”, Izv. Akad. Nauk SSSR Ser. Mat., vol. 25, no. 6, pp. 809–814 (In Russ.)Глускин Л. М. Полугруппы изотонных преобразований // УМН. 1961. Т. 16, №5. С. 157–162.Gluskin, L. M., 1961, “Semigroups of isotone transformations”, Uspekhi Mat. Nauk, vol. 16, no. 5, pp. 157–162 (In Russ.)Важенин Ю.М. Элементарные свойства полугрупп преобразований упорядоченных множеств // Алгебра и логика. 1970. Т. 9, №3. С. 281–301.Vazhenin, Yu. M., 1970, “Elementary properties of semigroups of transformations of ordered sets”, Algebra and logic, vol. 9, no. 3, pp. 281–301 (In Russ.)Важенин Ю.М. Об элементарной определяемости и элементарной характеризуемости классов рефлексивных графов // Изв. вузов. Матем. 1972. №7. С. 3–11.Vazhenin, Yu. M., 1972, “The elementary definability and elementary characterizability of classes of reflexive graphs”, Izv. Vyssh. Uchebn. Zaved. Mat., vol. 7, pp. 3–11 (In Russ.)Михалeв А. В. Кольца эндоморфизмов модулей и структуры подмодулей // Итоги науки и техн. Сер. Алгебра. Топол. Геом. 1974. Т. 12. С. 51–76.Mikhalev, A. V., 1976, “Endomorphism rings of modules, and lattices of submodules”, J Math Sci, vol. 5, no. 6, pp. 786–802.Улам С. Нерешенные математические задачи. М.: Наука, 1964. 168 с.Ulam, S. M., 1960, “A collection of mathematical problems”, Interscience, New York, 150 p.Jonsson B. Topics in Universal Algebras // Lecture Notes in Math. Springer-Verlag, 1972. Vol. 250. P. 230.Jonsson, B., 1972, “Topics in Universal Algebras”, Lecture Notes in Math. Springer-Verlag, vol. 250, 230 p.Харари Ф. Теория графов. М.: Мир, 1973. 300 с.Harary, F., 1969, “Graph Theory”, Addison Wesley, 288 p.Мальцев А. И. Алгебраические системы. М.: Наука. Физматлит, 1970. 392 с.Maltzev, A. I., 1970, “Algebraic systems”, Nauka. Fizmatlit, Moscow, 392 p. (In Russ.)Акимова С. А. Абстрактная характеристика полугруппы эндоморфизмов упорядоченного множества // Математика. Механика: cб. науч. тр. Саратов : Изд-во Сарат. ун-та. 2004. №6. С. 3–5.Akimova, S. A., 2004, “Abstract characterization of endomorphism semigroups of ordered sets”, Mathematika. Mekhanika: sb. nauch. tr. Saratov: Izd. Saratov State Un., no. 6, pp. 3–5. (In Russ.)Фарахутдинов Р. А. Относительно элементарная определимость класса универсальных графовых полуавтоматов в классе полугрупп // Изв. вузов. Матем. 2022. №1. С. 74–84.Farakhutdinov, R. A., 2022, “Relatively elementary definability of the class of universal graphic semiautomata in the class of semigroups”, Allerton Press, vol. 66, no. 1, pp. 62–70.Кейслер Г., Чен Ч. Ч. Теория моделей. М.: Мир, 1977. 616 с.Kejsler, H. J., Chang, C. C., 2013, “Model theory”, Dover Publications, 672 p.Molchanov V. A., Farakhutdinov R. A. On Concrete Characterization of Universal Graphic Automata // Lobachevskii Journal of Mathematics. 2022. Vol. 43, №3. P. 664–671.Molchanov, V. A., Farakhutdinov, R. A., 2022, “On Concrete Characterization of Universal Graphic Automata”, Lobachevskii Journal of Mathematics, vol. 43, iss. 3, pp. 664–671.Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970. 416 с.Kuratowski, K., Mostowski, A., 1698, “Set theory”, North-Holland, 417 p.

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