Izvestiya of Saratov University. Mathematics. Mechanics. Informatics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Izv. Saratov Univ. Math. Mech. Inform.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Izv. Saratov Univ. Math. Mech. Inform., 2020, Volume 20, Issue 1, Pages 42–50 (Mi isu827)  

Scientific Part
Mathematics

On definability of universal graphic automata by their input symbol semigroups

V. A. Molchanov, R. A. Farakhutdinov

Saratov State University, 83 Astrakhanskaya St., Saratov 410012, Russia

Abstract: Universal graphic automaton $\mathrm{Atm}(G,G')$ is the universally attracting object in the category of automata, for which the set of states is equipped with the structure of a graph $G$ and the set of output symbols is equipped with the structure of a graph $G'$ preserved by transition and output functions of the automata. The input symbol semigroup of the automaton is $S(G,G')=\mathrm{End} G \times \mathrm{Hom}(G,G').$ It can be considered as a derivative algebraic system of the mathematical object $\mathrm{Atm}(G,G')$ which contains useful information about the initial automaton. It is common knowledge that properties of the semigroup are interconnected with properties of the algebraic structure of the automaton. Hence, we can study universal graphic automata by researching their input symbol semigroups. For these semigroups it is interesting to study the problem of definability of universal graphic automata by their input symbol semigroups — under which conditions are the input symbol semigroups of universal graphic automata isomorphic. This is the subject we investigate in the present paper. The main result of our study states that the input symbol semigroups of universal graphic automata over reflexive graphs determine the initial automata up to isomorphism and duality of graphs if the state graphs of the automata contain an edge that does not belong to any cycle.

Key words: generalized Galois theory, automaton, graph, semigroup, isomorphism.

DOI: https://doi.org/10.18500/1816-9791-2020-20-1-42-50

Full text: PDF file (187 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.713.2
Received: 28.02.2019
Accepted:24.03.2019
Language:

Citation: V. A. Molchanov, R. A. Farakhutdinov, “On definability of universal graphic automata by their input symbol semigroups”, Izv. Saratov Univ. Math. Mech. Inform., 20:1 (2020), 42–50

Citation in format AMSBIB
\Bibitem{MolFar20}
\by V.~A.~Molchanov, R.~A.~Farakhutdinov
\paper On definability of universal graphic automata by their input symbol semigroups
\jour Izv. Saratov Univ. Math. Mech. Inform.
\yr 2020
\vol 20
\issue 1
\pages 42--50
\mathnet{http://mi.mathnet.ru/isu827}
\crossref{https://doi.org/10.18500/1816-9791-2020-20-1-42-50}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000529107100004}


Linking options:
  • http://mi.mathnet.ru/eng/isu827
  • http://mi.mathnet.ru/eng/isu/v20/i1/p42

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика
    Number of views:
    This page:45
    Full text:13
    References:2

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021