For citation:
Molchanov V. A., Khvorostukhina E. V. On Problem of Abstract Characterization of Universal Hypergraphic Automata. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2017, vol. 17, iss. 2, pp. 148-159. DOI: 10.18500/1816-9791-2017-17-2-148-159, EDN: ZEVWZR
On Problem of Abstract Characterization of Universal Hypergraphic Automata
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 Atm (H1,H2), where H1 is a hypergraph of the state set, H2 is a hypergraph of the set of output symbols and S = EndH1 × Hom(H1,H2) is a semigroup of input symbols. Such automata are called universal hypergraphic automata. The semigroup of input symbols S of such automaton Atm (H1,H2) 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.
- Plotkin B. I., Geenglaz L. Ja., Gvaramija А. А. Algebraic structures in automata and databases theory. Singapore, River Edge, NJ, World Scientific, 1992. 192 p. (Russ. ed. : Plotkin B. I., Geenglaz L. Ja., Gvaramija А. А. Elementy algebraicheskoi teorii avtomatov. Moscow, Vysshaia shkola, 1994. 192 p.)
- Ulam S. A Collection of Mathematical Problems. New York, Interscience Publ., 1960. 150 p. (Russ. ed. : Ulam S. Nereshennye matematicheskie zadachi. Moscow, Nauka, 1964. 168 p.)
- Jonsson B. Topics in universal algebra. Lecture Notes in Math. Berlin, Heidelberg, New York, Springer-Verlag, 1972. 220 p.
- 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, pp. 284–285 (in Russian).
- Bretto A. Hypergraph theory. An Introduction. Cham, Heidelberg, New York, Dordrecht, London, Springer, 2013. 133 p. DOI: https://doi.org/10.1007/978-3-319-00080-0.
- Hartshorne R. Foundations of Projective Geometry. New York, ISHI Press, 2009. 190 p. (Russ. ed. : Hartshorne R. Osnovy proektivnoi geometrii. Moscow, Mir, 1970. 161 p.)
- Molchanov A. V. Endomorphism semigroups of weak p-hypergraphs. Russian Math. (Iz. VUZ), 2000, vol. 44, no. 3, pp. 77–80.
- Molchanov A. V. Ob opredeljaemosti gipergraficheskih avtomatov ih vyhodnymi funkcijami [On definability of hypergraphic automata by their exist functions]. Teoreticheskie problemy informatiki [Theoretical Problems of Informatics], 1998, iss. 2, pp. 74–84 (in Russian).
- 847 reads