Indices of states in dynamical system of binary vectors associated with palms orientations

A. V. Zharkova

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 16 (2016) no. 4, pp. 475-484.

Résumé

Dynamical system of binary vectors associated with palms orientations is considered. A tree is called a palm with $s+c$ edges if it is a union of $c+1$ paths with common end vertex and all of these paths except perhaps one (with $s$ edges) have a length 1. The system splits into finite subsystems according to the dimension of states. States of a finite dynamical system ($B^{s+c}$,$\gamma$) are all possible orientations of a given palm with $s+c$ edges. They are naturally encoded by binary vectors and the evolutionary function $\gamma$ transforms a given palm orientation by reversing all arcs that enter sinks and there is no other difference between the given state and the next one. An algorithm to calculate indices of states in this dynamical system is proposed and it is proved that the depth of the basin of the finite dynamical system ($B^{s+c}$, $\gamma$), $s>0$, $c>1$, is equal to $s$.

Bibliographie

[1] Abrosimov M. B., Graph models of fault tolerance, Saratov Univ. Press, Saratov, 2012, 192 pp. (in Russian)

[2] Kurnosova S. G., “T-irreducible extensions for some classes of graphs”, Collection of scientific works, Theoretical Problems of computer science and its applications, 6, Saratov Univ. Press, Saratov, 2004, 113–125 (in Russian)

[3] Barbosa V. C., An atlas of edge-reversal dynamics, Chapman/CRC, Boca Raton, 2001, 385 pp. | MR | Zbl

[4] Colon-Reyes O., Laubenbacher R., Pareigis B., “Boolean monomial dynamical systems”, Annals of Combinatorics, 8 (2004), 425–439 | DOI | MR | Zbl

[5] Salii V. N., “A class of finite dynamical systems”, Tomsk State University Journal. Supplement, 2005, no. 14, 23–26 (in Russian)

[6] Vlasova A. V., The investigation of evolutionary parameters in dynamical systems of binary vectors, Certificate of state registration for comput. programs No 2009614409, registered in August 20, 2009, Rospatent (in Russian)

[7] Vlasova A. V., “Indices in dynamical system $(B, \delta)$ of binary vectors”, Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 11:3/1 (2011), 116–122 (in Russian) | MR

[8] Zharkova A. V., “Indices in dynamic system of binary vectors associated with cycles orientations”, Appl. Discrete Math., 2012, no. 2(16), 79–85 (in Russian)

[9] Vlasova A. V., “Dynamical systems defined by palm trees”, Computer Science and Information Technology, Proc. Intern. Sci. Conf., Saratov Univ. Press, Saratov, 2009, 57–60 (in Russian)

[10] Zharkova A. V., “Attractors in finite dynamic systems of binary vectors associated with palms orientations”, Appl. Discrete Math., 2014, no. 3(25), 58–67 (in Russian)

[11] Zharkova A. V., “On branching and immediate predecessors of the states in finite dynamic system of all possible orientations of a graph”, Appl. Discrete Math. Supplement, 2013, no. 6, 76–78 (in Russian)