On problem of abstract characterization of universal hypergraphic automata

V. A. Molchanov ; E. V. Khvorostukhina

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 17 (2017) no. 2, pp. 148-159.

Résumé

Hypergraphic automata are automata whose state sets and sets of output symbols are endowed with algebraic structures of hypergraphs preserving by transition and exit functions. Universally attracting objects in the category of hypergraphic automata are automata $\mathrm{Atm}\,(H_1 ,H_2)$, where $H_1$ is a hypergraph of the state set, $H_2$ is a hypergraph of the set of output symbols and $S=\mathrm{End}\, H_1\times \mathrm{Hom}\,(H_1,H_2)$ is a semigroup of input symbols. Such automata are called universal hypergraphic automata. The semigroup of input symbols $S$ of such automaton $\mathrm{Atm}\,(H_1 ,H_2)$ is a derivative algebra of mappings for such automaton. So its properties are interconnected with properties of the algebraic structure of the automaton. Thus we can study universal hypergraphic automata by investigation of their semigroups of input symbols. In this paper we study the problem of abstract characterization of universal hypergraphic automata. The problem is to find the conditions of existence of isomorpism of arbitrary automaton to the universal hypergraphic automaton. The main result of the paper is solving of this problem for universal hypergraphic automata over effective hypergraphs with $p$-definable edges. It's a wide and a very important class of automata because such algebraic systems contain automata whose state hypergraphs and hypergraphs of output symbols are projective or affine planes. Also they include automata whose state hypergraphs and hypergraphs of output symbols are divided into equivalence classes. To solve the main problem we also proved that the algebraic structure of effective hypergraps with $p$-definable edges were determined by a relation of $(p + 1)$-boundedness of vertices of this hypergraph and for automata under consideration, algebraic structures of state hypergraphs and hypergraphs of output symbols are determined by canonical relations of the semigroup of input symbols of the automata.

Bibliographie

[1] Plotkin B. I., Geenglaz L. Ja., Gvaramija A. A., Algebraic structures in automata and databases theory, World Scientific, Singapore, River Edge, NJ, 1992, 192 pp. | MR | Zbl

[2] Ulam S., A Collection of Mathematical Problems, Interscience Publ., New York, 1960, 150 pp. | MR | Zbl

[3] Jonsson B., Topics in universal algebra, Lecture Notes in Math., Springer-Verlag, Berlin–Heidelberg–N. Y., 1972, 220 pp. | DOI | MR | Zbl

[4] Molchanov V. A., Khvorostukhina E. V., “On problem of concrete characterization of universal hypergraphic automata”, Proc. VII Intern. Sci. Conf. “Computer Science and Information Technologies” (Saratov, 2016), 2016, 284–285 (in Russian) | Zbl

[5] Bretto A., Hypergraph theory. An Introduction, Springer, Cham–Heidelberg–N. Y.–Dordrecht–London, 2013, 133 pp. | DOI | MR | Zbl

[6] Hartshorne R., Foundations of Projective Geometry, ISHI Press, New York, 2009, 190 pp. | MR

[7] Molchanov A. V., “Endomorphism semigroups of weak $p$-hypergraphs”, Russian Math. (Iz. VUZ), 2000, no. 3, 80–83 | MR | Zbl

[8] Molchanov A. V., “On definability of hypergraphic automata by their exist functions”, Theoretical Problems of Informatics, 1998, no. 2, 74–84 (in Russian)