Для цитирования:
Molchanov V. A., Farakhutdinov R. A. On structure of isomorphisms of universal graphic automata [Молчанов В. А., Фарахутдинов Р. А. О структуре изоморфизмов универсальных графовых автоматов] // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2025. Т. 25, вып. 1. С. 34-45. DOI: 10.18500/1816-9791-2025-25-1-34-45, EDN: DEBJXL
On structure of isomorphisms of universal graphic automata
[О структуре изоморфизмов универсальных графовых автоматов]
Теория автоматов — один из разделов математической кибернетики, изучающий преобразователи информации, возникающие во многих прикладных задачах. Основная цель теории автоматов — разработка методов, с помощью которых можно описывать и анализировать динамическое поведение дискретных систем. В зависимости от исследуемых задач рассматриваются автоматы, у которых множество состояний и множество выходных сигналов наделены дополнительной математической структурой, согласованной с функциями переходов и выходов автомата. Мы исследуем автоматы над графами и называем их графовыми автоматами. Универсальный графовый автомат Atm(G,H) является универсально притягивающим объектом в категории таких автоматов. Полугруппа входных сигналов такого автомата имеет вид S(G,H)=End G×Hom(G,H). Её можно рассматривать как производную алгебраическую систему математического объекта Atm(G,H), содержащую полезную информацию об исходном автомате. Известно, что свойства полугруппы взаимосвязаны со свойствами алгебраической структуры автомата. Следовательно, можно изучать универсальные графовые автоматы, исследуя их полугруппы входных сигналов. Ранее авторы доказали, что широкий класс таких автоматов определяется (с точностью до изоморфизма) своими полугруппами входных сигналов. В данной работе исследуется связь изоморфизмов универсальных графовых автоматов с изоморфизмами их компонент — полугрупп входных сигналов и графов состояний и выходных сигналов.
- Plotkin B. I. Groups of automorphisms of algebraic systems. California, Wolters Noordhoff Publishing, 1972. 502 p. (Rus. ed. : Moscow, Nauka, 1966. 604 p.).
- Pinus A. G. Elementary equivalence of derived structures of free semigroups, unars, and groups. Algebra and Logic, 2004, vol. 43, iss 6, pp. 408–417. https://doi.org/10.1023/B:ALLO.0000048829.60182.48
- Pinus A. G. On the elementary equivalence of derived structures of free lattices. Russian Mathematics, 2002, iss. 5, pp. 44–47 (in Russian). EDN: HQUCWH
- Gluskin L. M. Semigroups and rings of endomorphisms of linear spaces. Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, 1959, vol. 23, iss. 6, pp. 841–870 (in Russian).
- Gluskin L. M. Semi-groups of isotone transformations. Uspekhi Matematicheskikh Nauk, 1961, vol. 16, iss. 5, pp. 157–162 (in Russian).
- Vazhenin Yu. M. Elementary properties of semigroups of transformations of ordered sets. Algebra and Logic, 1970, vol. 9, iss 3, pp. 169–179. https://doi.org/10.1007/BF02218675
- Vazhenin Yu. M. Elementary definability and elementary characterizability of classes of reflexive graphs. Izvestiya Vysshih Uchebnyh Zavedenij. Matematika, 1972, iss. 7, pp. 3–11 (in Russian).
- Mikhalev A. V. Endomorphism rings of modules and lattices of submodules. Journal of Soviet Mathematics, 1976, vol. 5, iss. 6, pp. 786–802. https://doi.org/10.1007/BF01085149
- Plotkin B. I., Greenglaz L. Ya., Gvaramiya A. A. Elementy algebraicheskoy teorii avtomatov [Elements of algebraic theory of automata]. Moscow, Vyshaja Shkola, 1994. 191 p. (in Russian).
- Molchanov V. A., Farakhutdinov R. A. On definability of universal graphic automata by their input symbol semigroups. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2020, vol. 20, iss. 1, pp. 42–50. https://doi.org/10.18500/1816-9791-2020-20-1-42-50
- Bogomolov A. M., Salii V. N. Algebraicheskie osnovy teorii diskretnykh sistem [Algebraic foundations of the theory of discrete systems]. Moscow, Nauka, 1997. 368 p. (in Russian).
- Harary F. Graph theory. Boston, Addison-Wesley Publishing Company, 1969. 270 p. (Russ. ed. : Moscow, Mir, 1973. 300 p.).
- Farakhutdinov R. A. Relatively elementary definability of the class of universal graphic semiautomata in the class of semigroups. Russian Mathematics, 2022, vol. 66, iss. 1, pp. 62–70. https://doi.org/10.3103/S1066369X22010029
- Kurosh A. G. Teoriya grupp [Group theory]. Moscow, Nauka, 1967. 648 p. (in Russian).
- 141 просмотр