Образец для цитирования:

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


Опубликована онлайн: 
02.03.2020
Язык публикации: 
английский
Рубрика: 
УДК: 
519.713.2

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 

Полный текст в формате PDF: