maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2018-5-561-571mais-757Research ArticleОригинальные статьиArticlesПредставление универсальных гиперграфических автоматов автономными выходными сигналамиUniversal Hypergraphic Automata Representation by Autonomous Input Symbolshttps://orcid.org/0000-0002-2775-5732ХворостухинаЕкатерина ВладимировнаKhvorostukhinaEkaterina

канд. физ.-мат. наук, доцент.

ул. Политехническая, 77, г. Саратов, 410054.

Ekaterina V. Khvorostukhina, PhD.

77 Politechnicheskaya str., Saratov 410054.

khvorostukhina85@gmail.comhttps://orcid.org/0000-0001-6509-3090МолчановВладимир АлександровичMolchanovVladimir

докт. физ.-мат. наук, профессор.

ул. Астраханская, 83, г. Саратов, 410012.

Vladimir A. Molchanov, PhD.

83 Astrakhanskaya str., Saratov, 410012.

molchanovva@mail.ruСаратовский государственный технический университет им. Гагарина Ю.А.РоссияYuri Gagarin State Technical University of Saratov.Russian FederationСаратовский национальный исследовательский государственный университет им. Н.Г. ЧернышевскогоРоссияSaratov State University.Russian Federation201828102018255561571Copyright © Хворостухина Е.В., Молчанов В.А., 20182018Хворостухина Е.В., Молчанов В.А.Khvorostukhina E., Molchanov V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/757

Гиперграфическими автоматами называются автоматы, у которых множества состояний и выходных символов наделены структурами гиперграфов, сохраняющимися функциями переходов и выходными функциями. Универсальные притягивающие объекты в категории таких автоматов представляются автоматами Atm(H1,H2) с гиперграфом состояний H1, гиперграфом выходных символов H2 и полугруппой входных символов S = EndH1 × Hom(H1,H2), которые называются универсальными гиперграфическими автоматами. Для такого автомата Atm(H1,H2) полугруппа входных символов S является производной алгеброй отображений, свойства которой взаимосвязаны со свойствами алгебраической структуры данного автомата. Это позволяет изучать универсальные гиперграфические автоматы с помощью исследования их полугрупп входных символов. В настоящей работе рассматривается проблема представления универсальных гиперграфических автоматов в их полугруппах входных сигналов: описывается представление универсального гиперграфического автомата в виде многосортной алгебраической системы, канонически построенной из автономных входных сигналов этого автомата. Эта конструкция является одним из инструментов доказательства относительно элементарной определимости рассматриваемых автоматов в классе полугрупп, которая позволяет проанализировать взаимосвязь элементарных свойств этих автоматов и их полугрупп входных сигналов. Основной результат работы дает решение этой задачи для универсальных гиперграфических автоматов над эффективными гиперграфами p-определимыми ребрами. Это достаточно широкий и весьма важный класс автоматов, так как он содержит, в частности, автоматы, у которых гиперграфы состояний и выходных символов являются плоскостями (например, проективными или аффинными) или разбиениями на классы нетривиальных эквивалентностей. Статья публикуется в авторской редакции.

Hypergraphic automata are automata with state sets and input symbol sets being hypergraphs which are invariant under actions of transition and output functions. Universally attracting objects of a category of hypergraphic automata are automata Atm(H1,H2). Here, H1 is a state hypergraph, H2 is classified as an output symbol hypergraph, and S = EndH1 × Hom(H1,H2) is an input symbol semigroup. Such automata are called universal hypergraphic automata. The input symbol semigroup S of such an automaton Atm(H1,H2) is an algebra of mappings for such an automaton. Semigroup properties are interconnected with properties of the algebraic structure of the automaton. Thus, we can study universal hypergraphic automata with the help of their input symbol semigroups. In this paper, we investigated a representation problem of universal hypergraphic automata in their input symbol semigroup. The main result of the current study describes a universal hypergraphic automaton as a multiple-set algebraic structure canonically constructed from autonomous input automaton symbols. Such a structure is one of the major tools for proving relatively elementary definability of considered universal hypergraphic automata in a class of semigroups in order to analyze interrelation of elementary characteristics of universal hypergraphic automata and their input symbol semigroups. The main result of the paper is the solution of this problem for universal hypergraphic automata for effective hypergraphs with p-definable edges. It is an important class of automata because such an algebraic structure variety includes automata with state sets and output symbol sets represented by projective or affine planes, along with automata with state sets and output symbol sets divided into equivalence classes. The article is published in the authors' wording.

автоматполугруппагиперграфвходной сигналautomatonsemigrouphypergraphinput symbolReferencesPlotkin B.I., Geenglaz L.Ja., Gvaramija A. A., Algebraic structures in automata and databases theory, World Scientific, Singapore, 1992.Plotkin B.I., Geenglaz L.Ja., Gvaramija A. A., Algebraic structures in automata and databases theory, World Scientific, Singapore, 1992.Simovici D., “On the theory of reduction of semilatticial automata”, Scientific Annals of the Alexandru loan Cuza University of Iasi (New Series), 22:1 (1976), 107-110.Simovici D., “On the theory of reduction of semilatticial automata”, Scientific Annals of the Alexandru loan Cuza University of Iasi (New Series), 22:1 (1976), 107-110.Gecseg F., “O proizvedeniyakh uporyadochennykh avtomatov. I”, Acta Sci. Math., 24:3-4 (1963), 244-250 (in Russian).Gecseg F., “O proizvedeniyakh uporyadochennykh avtomatov. I”, Acta Sci. Math., 24:3-4 (1963), 244-250 (in Russian).Gecseg F., “O proizvedeniyakh uporyadochennykh avtomatov. II”, Acta Sci. Math., 25:1-2 (1964), 124-128 (in Russian).Gecseg F., “O proizvedeniyakh uporyadochennykh avtomatov. II”, Acta Sci. Math., 25:1-2 (1964), 124-128 (in Russian).Eilenberg S., Automata, languages and machines. Volume B, Academic Press, New York, San Francisco, London, 1976.Eilenberg S., Automata, languages and machines. Volume B, Academic Press, New York, San Francisco, London, 1976.Bretto A., Hypergraph theory. An Introduction, Springer, Cham, 2013.Bretto A., Hypergraph theory. An Introduction, Springer, Cham, 2013.Hartshorne R., Foundations of Projective Geometry, Ishi Press, New York, 2009.Hartshorne R., Foundations of Projective Geometry, Ishi Press, New York, 2009.Molchanov V. A., Khvorostukhina E. V., “Ob abstraktnoy opredelyaemosti universalnykh gipergraficheskikh avtomatov polugruppami ikh vkhodnykh signalov”, Issledovaniya po algebre, teorii chisel, funktsionalnomu analizu i smezhnym voprosam, 2016, № 8, 67-69 (in Russian).Molchanov V. A., Khvorostukhina E. V., “Ob abstraktnoy opredelyaemosti universalnykh gipergraficheskikh avtomatov polugruppami ikh vkhodnykh signalov”, Issledovaniya po algebre, teorii chisel, funktsionalnomu analizu i smezhnym voprosam, 2016, № 8, 67-69 (in Russian).Molchanov V. A., Khvorostukhina E. V., “On problem of concrete characterization of universal automata”, Loba,chevskii Journal of Mathematics, 38:4 (2017), 664-669.Molchanov V. A., Khvorostukhina E. V., “On problem of concrete characterization of universal automata”, Loba,chevskii Journal of Mathematics, 38:4 (2017), 664-669.Ershov Yu. L., Problemy razreshimosti i konstruktivnye modeli, Nauka, Moscow, 1980 (in Russian).Ershov Yu. L., Problemy razreshimosti i konstruktivnye modeli, Nauka, Moscow, 1980 (in Russian).Molchanov A. V., “Endomorphism semigroups of weak p-hypergraphs”, Russian Mathematics (Izvestiya VUZ. Matematika,), 44:3 (2000), 77-80.Molchanov A. V., “Endomorphism semigroups of weak p-hypergraphs”, Russian Mathematics (Izvestiya VUZ. Matematika,), 44:3 (2000), 77-80.

The authors declare that there are no conflicts of interest present.