Elementary definability of the class of universal hypergraphic automata in the class of semigroups
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 hypergraphic automata are called universal hypergraphic automata. The semigrou...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Saratov State University
2022-08-01
|
| Series: | Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика |
| Subjects: | |
| Online Access: | https://mmi.sgu.ru/sites/mmi.sgu.ru/files/text-pdf/2022/08/293-306-molchanov-khvorostukhina_0.pdf |
| _version_ | 1817982199085924352 |
|---|---|
| author | Molchanov, Vladimir Aleksandrovich Khvorostukhina, Ekaterina Vladimirovna |
| author_facet | Molchanov, Vladimir Aleksandrovich Khvorostukhina, Ekaterina Vladimirovna |
| author_sort | Molchanov, Vladimir Aleksandrovich |
| collection | DOAJ |
| description | 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 hypergraphic automata are called universal hypergraphic automata. The semigroups of input symbols of such automata are derivative algebras of mappings for such automata. So their properties are interconnected with the properties of the algebraic structures of the automata. Thus, we can study universal hypergraphic automata by investigating their semigroups of input symbols. Earlier, the authors proved that such automata over hypergraphs from a fairly wide class are completely (up to isomorphism) determined by their semigroups of input symbols. In this paper, we prove the elementary definability of the class of such automata in the class of semigroups. The main result of the paper is the solving of this problem for universal hypergraphic automata over $p$-hypergraphs. It is a wide and very important class of automata because such algebraic systems contain automata whose state hypergraphs and hypergraphs of output symbols are projective or affine planes. The results show that the universal hypergraphic automaton over $p$-hypergraphs is represented as an algebraic system, constructed in the semigroup of input symbols of the automaton using the canonical relations of the automaton. These relations are determined by the formulas of the elementary theory of semigroups. Using such a representation of automata, an effective syntactic transformation of formulas of the elementary theory of hypergraphic automata into formulas of the elementary theory of semigroups is determined. It allows a comprehensive study of the relationship between the elementary properties of universal hypergraphic automata over $p$-hypergraphs and their semigroups of input symbols. |
| first_indexed | 2024-04-13T23:17:40Z |
| format | Article |
| id | doaj.art-935163b4e00b42f4b5595e8c83ba14e5 |
| institution | Directory Open Access Journal |
| issn | 1816-9791 2541-9005 |
| language | English |
| last_indexed | 2024-04-13T23:17:40Z |
| publishDate | 2022-08-01 |
| publisher | Saratov State University |
| record_format | Article |
| series | Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика |
| spelling | doaj.art-935163b4e00b42f4b5595e8c83ba14e52022-12-22T02:25:21ZengSaratov State UniversityИзвестия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика1816-97912541-90052022-08-0122329330610.18500/1816-9791-2022-22-3-293-306Elementary definability of the class of universal hypergraphic automata in the class of semigroupsMolchanov, Vladimir Aleksandrovich0Khvorostukhina, Ekaterina Vladimirovna1Saratov State University, Russia, 410026, Saratov, Astrahanskaya str., 83Yuri Gagarin State Technical University of Saratov, Russia, 410054, Saratov, Politekhnicheskaya st., 77Hypergraphic 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 hypergraphic automata are called universal hypergraphic automata. The semigroups of input symbols of such automata are derivative algebras of mappings for such automata. So their properties are interconnected with the properties of the algebraic structures of the automata. Thus, we can study universal hypergraphic automata by investigating their semigroups of input symbols. Earlier, the authors proved that such automata over hypergraphs from a fairly wide class are completely (up to isomorphism) determined by their semigroups of input symbols. In this paper, we prove the elementary definability of the class of such automata in the class of semigroups. The main result of the paper is the solving of this problem for universal hypergraphic automata over $p$-hypergraphs. It is a wide and very important class of automata because such algebraic systems contain automata whose state hypergraphs and hypergraphs of output symbols are projective or affine planes. The results show that the universal hypergraphic automaton over $p$-hypergraphs is represented as an algebraic system, constructed in the semigroup of input symbols of the automaton using the canonical relations of the automaton. These relations are determined by the formulas of the elementary theory of semigroups. Using such a representation of automata, an effective syntactic transformation of formulas of the elementary theory of hypergraphic automata into formulas of the elementary theory of semigroups is determined. It allows a comprehensive study of the relationship between the elementary properties of universal hypergraphic automata over $p$-hypergraphs and their semigroups of input symbols.https://mmi.sgu.ru/sites/mmi.sgu.ru/files/text-pdf/2022/08/293-306-molchanov-khvorostukhina_0.pdfelementary definabilityautomatonhypergraphsemigroup |
| spellingShingle | Molchanov, Vladimir Aleksandrovich Khvorostukhina, Ekaterina Vladimirovna Elementary definability of the class of universal hypergraphic automata in the class of semigroups Известия Саратовского университета. Новая серия. Серия Математика. Механика. Информатика elementary definability automaton hypergraph semigroup |
| title | Elementary definability of the class of universal hypergraphic automata in the class of semigroups |
| title_full | Elementary definability of the class of universal hypergraphic automata in the class of semigroups |
| title_fullStr | Elementary definability of the class of universal hypergraphic automata in the class of semigroups |
| title_full_unstemmed | Elementary definability of the class of universal hypergraphic automata in the class of semigroups |
| title_short | Elementary definability of the class of universal hypergraphic automata in the class of semigroups |
| title_sort | elementary definability of the class of universal hypergraphic automata in the class of semigroups |
| topic | elementary definability automaton hypergraph semigroup |
| url | https://mmi.sgu.ru/sites/mmi.sgu.ru/files/text-pdf/2022/08/293-306-molchanov-khvorostukhina_0.pdf |
| work_keys_str_mv | AT molchanovvladimiraleksandrovich elementarydefinabilityoftheclassofuniversalhypergraphicautomataintheclassofsemigroups AT khvorostukhinaekaterinavladimirovna elementarydefinabilityoftheclassofuniversalhypergraphicautomataintheclassofsemigroups |