Scholarlink

Abstract <p>The work is devoted to the algebraic theory of structured automata. We consider semigroup automata without output signals over graphs, which are called graphic semiautomata. We study partial graphic semiautomata, each input signal of which is a partial endomorphism of the state graph. In the category of partial graphic semiautomata over the graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G=(X,\rho)\)</EquationSource> <!--LobJMat2561392Farakhutdinov-m1--> </InlineEquation>, a special attention is paid to the semiautomaton <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\({\textrm{PAtm}(G)=(G,\textrm{PEnd}(G),\star)}\)</EquationSource> <!--LobJMat2561392Farakhutdinov-m2--> </InlineEquation> with semigroup <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\textrm{PEnd}(G)\)</EquationSource> <!--LobJMat2561392Farakhutdinov-m3--> </InlineEquation> of all partial endomorphisms of the graph <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(G\)</EquationSource> <!--LobJMat2561392Farakhutdinov-m4--> </InlineEquation>, since it is a universally attracting object in this category and is called a universal partial graphic semiautomaton. The main result of the work is the proof of the relatively elementary definability of the class of universal partial graphic semiautomata over nontrivial reflexive graphs in the class of semigroups, and applications of got relatively elementary definability.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Relatively Elementary Definability of the Class of Universal Partial Graphic Semiautomata over Nontrivial Reflexive Graphs in the Class of Semigroups

  • 期刊论文

  • 发表日期：

    2025年12月1日

查看全文
  • R. A. Farakhutdinov,
  • V. A. Molchanov

摘要

Abstract

The work is devoted to the algebraic theory of structured automata. We consider semigroup automata without output signals over graphs, which are called graphic semiautomata. We study partial graphic semiautomata, each input signal of which is a partial endomorphism of the state graph. In the category of partial graphic semiautomata over the graph \(G=(X,\rho)\) , a special attention is paid to the semiautomaton \({\textrm{PAtm}(G)=(G,\textrm{PEnd}(G),\star)}\) with semigroup \(\textrm{PEnd}(G)\) of all partial endomorphisms of the graph \(G\) , since it is a universally attracting object in this category and is called a universal partial graphic semiautomaton. The main result of the work is the proof of the relatively elementary definability of the class of universal partial graphic semiautomata over nontrivial reflexive graphs in the class of semigroups, and applications of got relatively elementary definability.