Elementary definability of the class of universal hypergraphic automata in the class of semigroups

V. A. Molchanov ; E. V. Khvorostukhina

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 22 (2022) no. 3, pp. 293-306.

Résumé

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.

Bibliographie

[1] Plotkin B. I., Greenglaz L. Ja., Gvaramija A. A., Algebraic Structures in Automata and Databases Theory, World Scientific, Singapore, River Edge, NJ, 1992, 296 pp. | MR | Zbl

[2] Molchanov V. A., Khvorostukhina E. V., “On problem of abstract definability of universal hypergraphic automata by input symbol semigroup”, Chebyshevskii Sbornik, 20:2 (70) (2019), 251–264 (in Russian) | DOI | MR

[3] Khvorostukhina E. V., Molchanov V. A., “Abstract characterization of input symbol semigroups of universal hypergraphic automata”, Lobachevskii Journal of Mathematics, 41:2 (2020), 214–226 | DOI | MR | Zbl

[4] Khvorostukhina E. V., Molchanov V. A., “Universal hypergraphic automata representation by autonomous input symbols”, Modeling and Analysis of Information Systems, 25:5 (77) (2018), 561–571 | DOI | MR

[5] Pinus A. G., Vazhenin Yu. M., “Elementary classification and decidability of theories of derived structures”, Russian Mathematical Surveys, 60:3 (2005), 395–432 | DOI | DOI | MR | Zbl

[6] Pinus A. G., “On the elementary equivalence of derived structures of free lattices”, Russian Mathematics (Izvestiya VUZ. Matematika), 46:5 (2002), 42–45 | MR | Zbl

[7] Pinus A. G., “Elementary equivalence of derived structures of free semigroups, unars, and groups”, Algebra and Logic, 43:6 (2004), 408–417 | DOI | MR | Zbl

[8] Pinus A. G., “Elementary equivalence for the lattices of subalgebras and automorphism groups of free algebras”, Siberian Mathematical Journal, 49:4 (2008), 692–695 (LLHUMD) | DOI | MR | Zbl

[9] Vazhenin Yu. M., “Elementary properties of semigroups of transformations of ordered sets”, Algebra and Logic, 9:3 (1970), 169–179 | DOI | MR | Zbl

[10] Vazhenin Yu. M., “The elementary definability and elementary characterizability of classes of reflexive graphs”, Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 1972, no. 7, 3–11 (in Russian) | Zbl

[11] Bunina E. I., Mikhalev A. V., “Elementary equivalence of endomorphism rings of Abelian $p$-groups”, Journal of Mathematical Sciences (New York), 137:6 (2006), 5212–5274 | DOI | MR | Zbl

[12] Ershov Yu. L., Problems of Decidability and Constructive Models, Nauka, M., 1980, 416 pp. (in Russian)

[13] Mal'cev A. I., Algebraic Systems, Springer, Berlin–Heidelberg, 1973, 320 pp. | DOI | MR | MR | Zbl

[14] Lallement G., Semigroups and Combinatorial Applications, Wiley, New York, 1979, 376 pp. | MR | Zbl

[15] Vagner V. V., “The theory of relations and the algebra of partial mappings”, Semigroup theory and its applications, 1, Saratov State University Publ., Saratov, 1965, 3–178 (in Russian)

[16] Bretto A., Hypergraph Theory. An Introduction, Springer, Cham, 2013, 119 pp. | DOI | MR | Zbl

[17] Kárteszi F., Introduction to Finite Geometries, North Holland, Hungary, 2014, 280 pp. | MR | MR