Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Zharkova A. V. Indices of States in Dynamical System of Binary Vectors Associated with Palms Orientations. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2016, vol. 16, iss. 4, pp. 475-484. DOI: 10.18500/1816-9791-2016-16-4-475-484, EDN: XHPYKF

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
Full text:
(downloads: 124)

Indices of States in Dynamical System of Binary Vectors Associated with Palms Orientations

Zharkova Anastasia Vladimirovna, Saratov State University

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 ,γ) are all possible orientations of a given palm with s + c edges. They are naturally encoded by binary vectors and the evolutionary function γ 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.

  1. Abrosimov M. B. Grafovye modeli otkazoustojchivosti [Graph models of fault tolerance]. Saratov, Saratov Univ. Press, 2012, 192 p. (in Russian).
  2. Kurnosova S. G. T-irreducible extensions for some classes of graphs. Teoreticheskie problemy informatiki i ee prilozhenii : sb. nauch. tr. [Theoretical Problems of computer science and its applications : collection of scientific works]. Saratov, Saratov Univ. Press, 2004, vol. 6, pp. 113–125 (in Russian).
  3. Barbosa V. C. An atlas of edge-reversal dynamics. Boca Raton, Chapman&Hall/CRC, 2001. 385 p.
  4. Colon-Reyes O., Laubenbacher R., Pareigis B. Boolean monomial dynamical systems. Ann. Combinatorics, 2004, vol. 8, pp. 425–439. DOI: https://doi.org/10.1007/s00026-004-0230-6.
  5. Salii V. N. A class of finite dynamical systems. Tomsk State University Journal. Supplement, 2005, no. 14, pp. 23–26 (in Russian).
  6. Issledovanie jevoljucionnyh parametrov v dinamicheskih sistemah dvoichnyh vektorov [The investigation of evolutionary parameters in dynamical systems of binary vectors] : Certificate of state registration for comput. programs № 2009614409 / Vlasova A. V.; issued by Rospatent. Registered in August 20, 2009 (in Russian).
  7. Vlasova A. V. Indices in dynamical system (B, δ) of binary vectors. Izv. Saratov Univ. (N. S.), Ser. Math. Mech. Inform., 2011, vol. 11, iss. 3, pt. 1, pp. 116–122 (in Russian).
  8. Zharkova A. V. Indices in dynamic system of binary vectors associated with cycles orientations. Appl. Discrete Math., 2012, no. 2 (16), pp. 79–85 (in Russian).
  9. Vlasova A. V. Dynamical systems defined by palm trees. Komp’juternye nauki i informacionnye tehnologii : Materialy Mezhdunar. nauch. konf. [Computer Science and Information Technology : Proc. Intern. Sci. Conf.]. Saratov, Sararov Univ. Press, 2009, pp. 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). pp. 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, pp. 76–78 (in Russian).