Geodesic
Iterative equitable partition of graph as a model of constant structure discrete time closed semantic system
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 10 (2017) no. 4, pp. 26-34 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Constant structure closed semantic systems are the systems each element of which receives its definition through the correspondent unchangeable set of other elements (neighbors) of the system. The definitions of the elements change iteratively and simultaneously based on the neighbor portraits from the previous iteration. In this paper, I study the behavior of such model systems, starting from the zero state, where all the system's elements are equal. The development of constant-structure discrete time closed semantic systems may be modelled as a discrete time coloring process on a connected graph. Basically, I consider the iterative redefinition process on the vertices only, assuming that the edges are plain connectors, which do not have their own colors and do not participate in the definition of the incident vertices. However, the iterative coloring process for both vertices and edges may be converted to the vertices-only coloring case by the addition of virtual vertices corresponding to the edges assuming the colors for the vertices and for the edges are taken from the same palette and assigned in accordance with the same laws. I prove that the iterative coloring (redefinition) process in the described model will quickly degenerate into a series of pairwise isomorphic states and discuss some directions of further research.
Keywords: closed semantic system; graph; isomorphism. 
@article{VYURU_2017_10_4_a2,
     author = {E. E. Ivanko},
     title = {Iterative equitable partition of graph as a model of constant structure discrete time closed semantic system},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {26--34},
     year = {2017},
     volume = {10},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2017_10_4_a2/}
}
TY  - JOUR
AU  - E. E. Ivanko
TI  - Iterative equitable partition of graph as a model of constant structure discrete time closed semantic system
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2017
SP  - 26
EP  - 34
VL  - 10
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VYURU_2017_10_4_a2/
LA  - en
ID  - VYURU_2017_10_4_a2
ER  - 
%0 Journal Article
%A E. E. Ivanko
%T Iterative equitable partition of graph as a model of constant structure discrete time closed semantic system
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2017
%P 26-34
%V 10
%N 4
%U http://geodesic.mathdoc.fr/item/VYURU_2017_10_4_a2/
%G en
%F VYURU_2017_10_4_a2
E. E. Ivanko. Iterative equitable partition of graph as a model of constant structure discrete time closed semantic system. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 10 (2017) no. 4, pp. 26-34. http://geodesic.mathdoc.fr/item/VYURU_2017_10_4_a2/

[1] Bloom P., How Children Learn the Meanings of Words, MIT Press, Cambridge, 2002

[2] Papadimitriou C. H., Computational Complexity, Pearson, London, 1993

[3] Godsil C. D., Algebraic Combinatorics, Chapman and Hall, London, 1993 | MR | Zbl

[4] Unger S. H., “GIT – a Heuristic Program for Testing Pairs of Directed Line Graphs for Isomorphism”, Communications of the ACM, 7:1 (1964), 26–34 | DOI | Zbl

[5] Weisfeiler B., Lehman A. A., “A Reduction of a Graph to a Canonical Form and an Algebra Arising During This Reduction”, Scientific-Technical Information, 2:9 (1968), 12–16 (in Russian)

[6] Arlazarov V. L., Zuev I. I., Uskov A. V., Faradzhev I. A., “An Algorithm for the Reduction of Finite Non-Oriented Graphs to Canonical Form”, USSR Computational Mathematics and Mathematical Physics, 14:3 (1974), 195–201 | DOI | MR

[7] McKay B. D., Piperno A., “Practical Graph Isomorphism”, Journal of Symbolic Computation, 60 (2014), 94–112 | DOI | MR | Zbl

[8] Syvanen M., “Horizontal Gene Transfer: Evidence and Possible Consequences”, Annual Review of Genetics, 28:1 (1994), 237–261 | DOI