<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">cheb</journal-id><journal-title-group><journal-title xml:lang="ru">Чебышевский сборник</journal-title><trans-title-group xml:lang="en"><trans-title>Chebyshevskii Sbornik</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">2226-8383</issn><publisher><publisher-name>Tula State Lev Tolstoy  Pedagogical University</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.22405/2226-8383-2019-20-2-259-272</article-id><article-id custom-type="elpub" pub-id-type="custom">cheb-610</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>Статьи</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="en"><subject>Article</subject></subj-group></article-categories><title-group><article-title>Об абстрактной определяемости универсальных гиперграфических автоматов полугруппами входных сигналов</article-title><trans-title-group xml:lang="en"><trans-title>On problem of abstract definability of universal hypergraphic automata by input symbol semigroup</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Молчанов</surname><given-names>Владимир Александрович</given-names></name><name name-style="western" xml:lang="en"><surname>Molchanov</surname><given-names>Vladimir Alexandrovich</given-names></name></name-alternatives><email xlink:type="simple">v.molchanov@inbox.ru</email></contrib><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Хворостухина</surname><given-names>Екатерина Владимировна</given-names></name><name name-style="western" xml:lang="en"><surname>Khvorostukhina</surname><given-names>Ekaterina Vladimirovna</given-names></name></name-alternatives><email xlink:type="simple">khvorostukhina85@gmail.com</email></contrib></contrib-group><pub-date pub-type="collection"><year>2019</year></pub-date><pub-date pub-type="epub"><day>23</day><month>01</month><year>2020</year></pub-date><volume>20</volume><issue>2</issue><fpage>259</fpage><lpage>272</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Молчанов В.А., Хворостухина Е.В., 2019</copyright-statement><copyright-year>2019</copyright-year><copyright-holder xml:lang="ru">Молчанов В.А., Хворостухина Е.В.</copyright-holder><copyright-holder xml:lang="en">Molchanov V.A., Khvorostukhina E.V.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://www.chebsbornik.ru/jour/article/view/610">https://www.chebsbornik.ru/jour/article/view/610</self-uri><abstract><p>Гиперграфическими автоматами называются автоматы, у которых множества состояний и выходных символов наделены структурами гиперграфов, сохраняющимися функциями переходов и выходными функциями. Универсальные притягивающие объекты в категории таких автоматов называются универсальными гиперграфическими автоматами. Для таких автоматов полугруппы входных символов являются производными алгебрами отображений, свойства которых взаимосвязаны со свойствами алгебраических структур данных автоматов. Это позволяет изучать универсальные гиперграфические автоматы с помощью исследования их полугрупп входных символов. В работе исследуется проблема абстрактной определяемости таких автоматов их полугруппами входных символов, суть которой заключается в нахождении условий изоморфности полугрупп входных символов универсальных гиперграфических автоматов. Основной результат работы дает решение этой задачи для универсальных гиперграфических автоматов над эффективными гиперграфами с p−определимыми ребрами. Это достаточно широкий и весьма важный класс автоматов, так как он содержит, в частности, автоматы, у которых гиперграфы состояний и выходных символов являются плоскостями (например, проективными или аффинными), а также автоматы, у которых множества состояний и выходных символов разбиваются на классы некоторой эквивалентности без одноэлементных классов. В настоящей работе доказано, что универсальные гиперграфические автоматы над эффективными гиперграфами с p−определимыми ребрами полностью (с точностью до изоморфизма) определяются своими полугруппами входных символов, а также описано строение измоморфизмов таких автоматов.</p></abstract><trans-abstract xml:lang="en"><p>Hypergraphic automata are automata, state sets and output symbol sets of which are hypergraphs, being invariant under actions of transition and output functions. Universally attracting objects in the category of such automata are called universal hypergraphic automata. The semigroups of input symbols of such automata are derivative algebras of mappings for such automata. Semigroup properties are interconnected with properties of the automaton. Therefore, we can study universal hypergraphic automata by investigation of their input symbol semigroups. In this paper, we solve a problem of abstract definability of such automata by their input symbol semigroups. This problem is to find the conditions of isomorphism of semigroups of input symbols of universal hypergraphic automata. The main result of the paper is the solving of this problem for universal hypergraphic automata over effective hypergraphs with p−definable edges. It is a wide and a very important class of automata because such algebraic systems contain automata whose state hypergraphs and output symbol hypergraphs are projective or affine planes. Also they include automata whose state hypergraphs and output symbol hypergraphs are divided into equivalence classes without singleton classes. In the current study, we proved that such automata were determined up to isomorphism by their input symbol semigroups and we described the structure of isomorphisms of such automata.</p></trans-abstract></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Плоткин Б. И., Гринглаз Л. Я., Гварамия А. А. Элементы алгебраической теории автоматов. М.: Высшая школа, 1994. 192 с.</mixed-citation><mixed-citation xml:lang="en">Plotkin, B. I., Geenglaz, L. Ja., Gvaramija, А. А. 1992, Algebraic structures in automata and databases theory, River Edge, World Scientific, Singapore, NJ, 192 p.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Molchanov V. A. Semigroups of mappings on graphs // Semigroup Forum. 1983. № 27. P. 155–199.</mixed-citation><mixed-citation xml:lang="en">Molchanov, V. A. 1983, “Semigroups of mappings on graphs“, Semigroup Forum, № 27, pp. 155–199.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Свердловская тетрадь: Сборник нерешенных проблем теории полугрупп. Свердловск: Урал. гос. ун-т, 1979. 41 с.</mixed-citation><mixed-citation xml:lang="en">Sverdlovskaja tetrad: Sb. nereshjonnyh zadach po teorii polugrupp. [Sverdlovsk notebook: A collection of unsolved problems of semigroup theory], 1979, Ural. univ., Sverdlovsk, 41 p.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">Лендер В. Б. Об эндоморфизмах проективных геометрий // Исследования алгебраических систем (Матем.записки Урал. ун-та). 1984. С. 48–50.</mixed-citation><mixed-citation xml:lang="en">Lender, V. B. 1984, “On edomorphisms of projective geometries“, Issledovanija algebraicheskih sistem (Matem. zapiski Ural.un.), pp. 48–50.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">Молчанов В. А. Как проективные плоскости определяются своими полугруппами // Теория полугрупп и ее приложения. Полугруппы и связанные с ними алгебраические системы, Саратов. гос. ун-т. 1984. C. 42–50.</mixed-citation><mixed-citation xml:lang="en">Molchanov V. A. 1984,“Projective planes are determined by their semigroups“, Teorija polugrupp i ejo prilozhenija. Polugruppy i svjazannye s nimi algebraicheskie sistemy, pp. 42–50.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Molchanov V. A universal planar automaton is determined by its semigroup of input symbols // Semigroup Forum. 2011. № 82. P.1–9.</mixed-citation><mixed-citation xml:lang="en">Molchanov, V. 2011, “A universal planar automaton is determined by its semigroup of input symbols“, Semigroup Forum, № 82, pp. 1–9.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">Bretto A. Hypergraph theory. An Introduction. Cham: Springer, 2013. 133 p. DOI: 10.1007/978-3-319-00080-0.</mixed-citation><mixed-citation xml:lang="en">Bretto, A. 2013, Hypergraph theory. An Introduction. Springer, Cham, 133 p. doi: 10.1007/978-3-319-00080-0</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">Улам С. Нерешенные математические задачи. М. : Наука, 1964. 168 с.</mixed-citation><mixed-citation xml:lang="en">Ulam, S. 1960, A Collection of Mathematical Problems. Interscience, New York, 168 p.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">Молчанов В. А., Хворостухина Е. В. О задаче абстрактной характеризации универсальных гиперграфических автоматов // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. - Саратов: Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского, 2017. Т. 17, № 2. C. 148–159.</mixed-citation><mixed-citation xml:lang="en">Molchanov, V. A., Khvorostukhina, E. V. 2017, “On problem of abstract characterization of universal hypergraphic automata “, Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., vol. 17, iss. 2, pp. 148-–159.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Молчанов В. А., Хворостухина Е. В. Об абстрактной определяемости универсальных гиперграфических автоматов полугруппами их входных сигналов // Материалы XIV Международной конференции .Алгебра и теория чисел: современные проблемы и приложения., посвященная 70-ти летию со дня рождения С. М. Воронина и Г. И. Архипова. – Саратов: Изд-во Саратовского гос. ун-та, Издательский центр .Наука., 2016. С. 67–69.</mixed-citation><mixed-citation xml:lang="en">Molchanov, V. A., Khvorostukhina, E. V. 2016, “On problem of abstract definability of universal hypergraphic automata by semigroups of their input symbols“, Materialy XIV Mezhdunarodnoj konferencii “Algebra i teorija chisel: sovremennye problemy i prilozhenija“, posvjashhennaja 70-ti letiju so dnja rozhdenija S.M. Voronina i G.I. Arhipova (XIV Int. Conf. “Algebra and Number theory“), Saratov, pp. 67–69.</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">Клиффорд А., Престон Г. Алгебраическая теория полугрупп. М. : Мир, 1972. Т. 1. 286 с.</mixed-citation><mixed-citation xml:lang="en">Clifford, А. H., Preston, G. B. 1961,The algebraic theory of semigroups, volume 1, American Mathematical society, Providence, 224 p.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Вагнер В. В. Теория отношений и алгебра частичных отображений // Теория полугрупп и ее приложения; Сб. научн. тр. 1965. № 1. С. 3–178.</mixed-citation><mixed-citation xml:lang="en">Vagner, V. V. 1965, “Relation theory and algebra of partial mappings“, Teorija polugrup i ejo prilozhenija, sbornik nauch.trud., № 1, pp. 3–178.</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">Молчанов А. В. Полугруппы эндоморфизмов слабых p−гиперграфов // Известия вузов. Математика. Саратов. 2000. № 3(454). С. 80–83.</mixed-citation><mixed-citation xml:lang="en">Molchanov, A. V. 2000, “Endomorphism semigroups of weak p-hypergraphs“, Russian Mathematics (Izvestiya VUZ. Matematika), vol. 44, № 3, pp. 77–80.</mixed-citation></citation-alternatives></ref><ref id="cit14"><label>14</label><citation-alternatives><mixed-citation xml:lang="ru">Molchanov A. V. On definability of hypergraphs by their semigroups of homomorphisms // Semigroup Forum. 2001. № 62. P. 53–65.</mixed-citation><mixed-citation xml:lang="en">Molchanov, A. V. 2001, “On definability of hypergraphs by their semigroups of homomorphisms“, Semigroup Forum, № 62, pp. 53–65.</mixed-citation></citation-alternatives></ref><ref id="cit15"><label>15</label><citation-alternatives><mixed-citation xml:lang="ru">Молчанов А. В. Об определяемости гиперграфических автоматов их выходными функциями // Теоретические проблемы информатики и ее приложений. Саратов. 1998. № 2. С. 74–84.</mixed-citation><mixed-citation xml:lang="en">Molchanov, A. V. 1998, “Ob opredeljaemosti gipergraficheskih avtomatov ih vyhodnymi funkcijami“, Teoreticheskie problemy informatiki, iss. 2, pp. 74–84.</mixed-citation></citation-alternatives></ref><ref id="cit16"><label>16</label><citation-alternatives><mixed-citation xml:lang="ru">Хартсхорн Р. Основы проективной геометрии. М.: Мир, 1970. 161 с.</mixed-citation><mixed-citation xml:lang="en">Hartshorne, R. 2009, Foundations of Projective Geometry, New York, 190 p.</mixed-citation></citation-alternatives></ref><ref id="cit17"><label>17</label><citation-alternatives><mixed-citation xml:lang="ru">Хворостухина Е. В. Об одном классе гиперграфических автоматов // Теорет. проблемы информатики и ее приложений. Саратов. 2008. № 8. С. 112–118.</mixed-citation><mixed-citation xml:lang="en">Khvorostukhina, E. V. 2008, “On a class of hypergraphic automata“, Teoreticheskie problem informatiki and its applications, Saratov, iss. 8, pp. 112–118.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
