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.