On problem of abstract definability of universal hypergraphic automata by input symbol semigroup
https://doi.org/10.22405/2226-8383-2019-20-2-259-272
Abstract
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 such automata are called universal hypergraphic automata. The semigroups of input symbols of such automata are derivative algebras of mappings for such automata. Semigroup properties are interconnected with properties of the automaton. Therefore, we can study universal hypergraphic automata by investigation of their input symbol semigroups. In this paper, we solve a problem of abstract definability of such automata by their input symbol semigroups. This problem is to find the conditions of isomorphism of semigroups of input symbols of universal hypergraphic automata. The main result of the paper is the solving of this problem for universal hypergraphic automata over effective hypergraphs with p−definable edges. It is a wide and a very important class of automata because such algebraic systems contain automata whose state hypergraphs and output symbol hypergraphs are projective or affine planes. Also they include automata whose state hypergraphs and output symbol hypergraphs are divided into equivalence classes without singleton classes. In the current study, we proved that such automata were determined up to isomorphism by their input symbol semigroups and we described the structure of isomorphisms of such automata.
About the Authors
Vladimir Alexandrovich MolchanovRussian Federation
Ekaterina Vladimirovna Khvorostukhina
Russian Federation
References
1. Plotkin, B. I., Geenglaz, L. Ja., Gvaramija, А. А. 1992, Algebraic structures in automata and databases theory, River Edge, World Scientific, Singapore, NJ, 192 p.
2. Molchanov, V. A. 1983, “Semigroups of mappings on graphs“, Semigroup Forum, № 27, pp. 155–199.
3. Sverdlovskaja tetrad: Sb. nereshjonnyh zadach po teorii polugrupp. [Sverdlovsk notebook: A collection of unsolved problems of semigroup theory], 1979, Ural. univ., Sverdlovsk, 41 p.
4. Lender, V. B. 1984, “On edomorphisms of projective geometries“, Issledovanija algebraicheskih sistem (Matem. zapiski Ural.un.), pp. 48–50.
5. Molchanov V. A. 1984,“Projective planes are determined by their semigroups“, Teorija polugrupp i ejo prilozhenija. Polugruppy i svjazannye s nimi algebraicheskie sistemy, pp. 42–50.
6. Molchanov, V. 2011, “A universal planar automaton is determined by its semigroup of input symbols“, Semigroup Forum, № 82, pp. 1–9.
7. Bretto, A. 2013, Hypergraph theory. An Introduction. Springer, Cham, 133 p. doi: 10.1007/978-3-319-00080-0
8. Ulam, S. 1960, A Collection of Mathematical Problems. Interscience, New York, 168 p.
9. Molchanov, V. A., Khvorostukhina, E. V. 2017, “On problem of abstract characterization of universal hypergraphic automata “, Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., vol. 17, iss. 2, pp. 148-–159.
10. Molchanov, V. A., Khvorostukhina, E. V. 2016, “On problem of abstract definability of universal hypergraphic automata by semigroups of their input symbols“, Materialy XIV Mezhdunarodnoj konferencii “Algebra i teorija chisel: sovremennye problemy i prilozhenija“, posvjashhennaja 70-ti letiju so dnja rozhdenija S.M. Voronina i G.I. Arhipova (XIV Int. Conf. “Algebra and Number theory“), Saratov, pp. 67–69.
11. Clifford, А. H., Preston, G. B. 1961,The algebraic theory of semigroups, volume 1, American Mathematical society, Providence, 224 p.
12. Vagner, V. V. 1965, “Relation theory and algebra of partial mappings“, Teorija polugrup i ejo prilozhenija, sbornik nauch.trud., № 1, pp. 3–178.
13. Molchanov, A. V. 2000, “Endomorphism semigroups of weak p-hypergraphs“, Russian Mathematics (Izvestiya VUZ. Matematika), vol. 44, № 3, pp. 77–80.
14. Molchanov, A. V. 2001, “On definability of hypergraphs by their semigroups of homomorphisms“, Semigroup Forum, № 62, pp. 53–65.
15. Molchanov, A. V. 1998, “Ob opredeljaemosti gipergraficheskih avtomatov ih vyhodnymi funkcijami“, Teoreticheskie problemy informatiki, iss. 2, pp. 74–84.
16. Hartshorne, R. 2009, Foundations of Projective Geometry, New York, 190 p.
17. Khvorostukhina, E. V. 2008, “On a class of hypergraphic automata“, Teoreticheskie problem informatiki and its applications, Saratov, iss. 8, pp. 112–118.
Review
For citations:
Molchanov V.A., Khvorostukhina E.V. On problem of abstract definability of universal hypergraphic automata by input symbol semigroup. Chebyshevskii Sbornik. 2019;20(2):259-272. (In Russ.) https://doi.org/10.22405/2226-8383-2019-20-2-259-272
Views:
508
Email this article 