For citation:
Molchanov V. A., Khvorostukhina E. V. Elementary definability of the class of universal hypergraphic automata in the class of semigroups. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2022, vol. 22, iss. 3, pp. 293-306. DOI: 10.18500/1816-9791-2022-22-3-293-306, EDN: MDACEG
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 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.
- Plotkin B. I., Greenglaz L. Ja., Gvaramija А. А. Algebraic Structures in Automata and Databases Theory. Singapore, River Edge, NJ, World Scientific, 1992. 296 p. (Russ. ed.: Moscow, Vysshaya shkola, 1994. 192 p.).
- Molchanov V. A., Khvorostukhina E. V. On problem of abstract definability of universal hypergraphic automata by input symbol semigroup. Chebyshevskii Sbornik, 2019, vol. 20, iss. 2 (70), pp. 251–264 (in Russian). https://doi.org/10.22405/2226-8383-2019-20-2-251-264
- Khvorostukhina E. V., Molchanov V. A. Abstract characterization of input symbol semigroups of universal hypergraphic automata. Lobachevskii Journal of Mathematics, 2020, vol. 41, iss. 2, pp. 214–226. https://doi.org/10.1134/S1995080220020109
- Khvorostukhina E. V., Molchanov V. A. Universal hypergraphic automata representation by autonomous input symbols. Modeling and Analysis of Information Systems, 2018, vol. 25, iss. 5 (77), pp. 561–571. https://doi.org/10.18255/1818-1015-2018-5-561-571
- Pinus A. G., Vazhenin Yu. M. Elementary classification and decidability of theories of derived structures. Russian Mathematical Surveys, 2005, vol. 60, iss. 3, pp. 395–432. https://dx.doi.org/10.1070/RM2005v060n03ABEH000847
- Pinus A. G. On the elementary equivalence of derived structures of free lattices. Russian Mathematics (Izvestiya VUZ. Matematika), 2002, vol. 46, iss. 5, pp. 42–45.
- Pinus A. G. Elementary equivalence of derived structures of free semigroups, unars, and groups. Algebra and Logic, 2004, vol. 43, iss. 6, pp. 408–417. https://doi.org/10.1023/B:ALLO.0000048829.60182.48
- Pinus A. G. Elementary equivalence for the lattices of subalgebras and automorphism groups of free algebras. Siberian Mathematical Journal, 2008, vol. 49, iss. 4, pp. 692–695. https://doi.org/10.1007/s11202-008-0066-0, EDN: LLHUMD
- Vazhenin Yu. M. Elementary properties of semigroups of transformations of ordered sets. Algebra and Logic, 1970, vol. 9, iss. 3, pp. 169–179. https://doi.org/10.1007/BF02218675
- Vazhenin Yu. M. The elementary definability and elementary characterizability of classes of reflexive graphs. Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 1972, iss. 7, pp. 3–11 (in Russian).
- Bunina E. I., Mikhalev A. V. Elementary equivalence of endomorphism rings of Abelian p-groups. Journal of Mathematical Sciences (New York), 2006, vol. 137, iss. 6, pp. 5212–5274. https://doi.org/10.1007/s10958-006-0296-2
- Ershov Yu. L. Problemy razreshimosti i konstruktivnye modeli [Problems of Decidability and Constructive Models]. Moscow, Nauka, 1980. 416 p. (in Russian).
- Mal’cev A. I. Algebraic Systems. Springer, Berlin, Heidelberg, 1973. 320 p. https://doi.org/10.1007/978-3-642-65374-2 (Russ ed.: Moscow, Nauka, 1970. 392 p.).
- Lallement G. Semigroups and Combinatorial Applications. New York, Wiley, 1979. 376 p.
- Vagner V. V. The theory of relations and the algebra of partial mappings. Teoriya polugrupp i eye prilozheniya [Semigroup theory and its applications]. Saratov, Saratov State University Publ., 1965. Iss. 1, pp. 3–178 (in Russian).
- Bretto A. Hypergraph Theory. An Introduction. Cham, Springer, 2013. 119 p. https://doi.org/10.1007/978-3-319-00080-0
- Karteszi F. Introduction to Finite Geometries. Hungary, North Holland, 2014. 280 p. (Russ. ed.: Moscow, Nauka, 1980. 320 p.).
- 1093 reads