Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)


Для цитирования:

Molchanov V. A., Farakhutdinov R. A. On Definability of Universal Graphic Automata by Their Input Symbol Semigroups [Молчанов В. А., Фарахутдинов Р. А. Об определяемости универсальных графических автоматов своими полугруппами входных сигналов] // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2020. Т. 20, вып. 1. С. 42-50. DOI: 10.18500/1816-9791-2020-20-1-42-50, EDN: UEIFDI


Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
02.03.2020
Полный текст:
(downloads: 408)
Язык публикации: 
английский
Рубрика: 
Тип статьи: 
Научная статья
УДК: 
519.713.2
EDN: 
UEIFDI

On Definability of Universal Graphic Automata by Their Input Symbol Semigroups
[Об определяемости универсальных графических автоматов своими полугруппами входных сигналов]

Авторы: 
Молчанов Владимир Александрович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Фарахутдинов Ренат Абуханович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

Универсальный графический автомат Atm(G, G′ ) — это универсально притягивающий объект в категории автоматов, у которых множество состояний наделено структурой графа G и множество выходных сигналов — структурой графа G′ , сохраняющимися функциями переходов и выходов автоматов. Полугруппа входных сигналов такого автомата имеет вид S(G, G′ ) = End G × Hom(G, G′ ). Она может рассматриваться как производная алгебраическая система математического объекта Atm(G, G′ ), которая содержит полезную информацию об исходном объекте. Хорошо известно, что свойства такой полугруппы взаимосвязаны со свойствами алгебраической структуры автомата. Следовательно, универсальные графические автоматы можно изучать путем исследования их полугрупп входных сигналов. Для таких полугрупп представляет интерес проблема определяемости универсальных графических автоматов своими полугруппами входных сигналов: при каких условиях полугруппы входных сигналов универсальных графических автоматов будут изоморфны. В данной работе мы исследовали эту проблему. Основной результат нашей работы состоит в том, что универсальные графические автоматы над рефлексивными графами определяются полугруппами своих входных сигналов с точностью до изоморфизма и двойственности графов, если в графе состояний автомата найдется дуга, не входящая ни в один орцикл. 

Список источников: 
  1. Plotkin B. I. Groups of Automorphisms of Algebraic Systems. Groningen, The Netherlands, WoLters-Noordhoff Publ., 1972. 502 p.
  2. Pinus A. G. On the elementary equivalence of derived structures of free lattices. Russian Math. (Iz. VUZ), 2002, vol. 46, no. 5, pp. 42–45.
  3. Pinus A. G. Elementary Equivalence of Derived Structures of Free Semigroups. Algebra and Logic, 2004, vol. 43, no. 6, pp. 408–417. DOI: https://doi.org/10.1023/B:ALLO.0000048829.60182.48
  4. Gluskin L. M. Semigroups and rings of endomorphisms of linear spaces. Izv. Akad. Nauk SSSR. Ser. Mat., 1959, vol. 23, iss. 6, pp. 841–870 (in Russian).
  5. Gluskin L. M. Semi-groups of isotone transformations. Uspekhi Mat. Nauk, 1961, vol. 16, iss. 5 (101), pp. 157–162 (in Russian).
  6. Vazhenin Yu. M. Ordered sets and their inf-endomorphisms. Math. Notes, 1970, vol. 7, iss. 3, pp. 204–208. DOI: https://doi.org/10.1007/BF01093116
  7. Vazhenin Yu. M. The elementary definability and elementary characterizability of classes of reflexive graphs. Izv. Vyssh. Uchebn. Zaved. Mat., 1972, no. 7, pp. 3–11 (in Russian).
  8. Markov V. T., Mikhalev A. V., Skornyakov L. A., Tuganbaev A. A. Rings of endomorphisms of modules and lattices of submodules. J. Soviet Math., 1985, vol. 31, iss. 3, pp. 3005–3051. DOI: https://doi.org/10.1007/BF02106808
  9. Ulam S. M. A Collection of Mathematical Problems. NewYork, Interscience, 1960. 150 p.
  10. Plotkin B. I., Greenglaz L. Ja., Gvaramija A. A. Algebraic structures in automata and databases theory. River Edge, NJ, World Scientific Publ. Co., 1992. 296 p.
  11. Molchanov V. A. Semigroups of mappings on graphs. Semigroup Forum, 1983, vol. 27, pp. 155–199. DOI: https://doi.org/10.1007/BF02572738
  12. Molchanov V. A., Farakhutdinov R. A. On universal graphic automata. In: Komp’iuternye nauki i informatsionnye tekhnologii: materialy mezhdunarodnoy nauchnoy konferentsii [Computer Science and Information Technologies: Materials of the Int. Sci. Conf.]. Saratov, Izdatel’skii tsentr “Nauka”, 2018, pp. 276–279 (in Russian).
  13. Clifford A. H., G. B. Preston. The algebraic theory of semigroups. Providence, RI, Amer. Math. Soc., 1964. 224 p.
  14. 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).
  15. Harary F. Graph Theory. Reading, MA, Addison-Wesley, 1969. 274 p.
  16. Molchanov V. A. A universal planar automaton is determined by its semigroup of input symbols. Semigroup Forum, 2011, vol. 82, iss. 1, pp. 1–9. DOI: https://doi.org/10.1007/s00233-010-9256-8
Поступила в редакцию: 
28.02.2019
Принята к публикации: 
24.03.2019
Опубликована: 
02.03.2020