On number of inaccessible states in finite dynamic systems of binary vectors associated with palms orientations

A. V. Zharkova

Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 115-117

Résumé

Finite dynamic systems of binary vectors associated with palms orientations are considered. A palm is a tree which is a union of paths having a common end vertex and all these paths, except perhaps one, have the length 1. States of a dynamic system $(P_{s+c},\gamma)$, $s>0$, $c>1$, are all possible orientations of a palm with trunk length $s$ and leafs number $c$, and evolutionary function transforms a given palm orientation by reversing all arcs that enter into sinks. This dynamic system is isomorphic to finite dynamic system ($B^{s+c}$, $\gamma$), $s>0$, $c>1$, where states of this system are all possible binary vectors of dimension $s+c$. Let $v=v_1\dots v_s.v_{s+1}\dots v_{s+c}\in B^{s+c}$, then $\gamma(v)=v'$ where $v'$ is obtained by simultaneous application of the following rules: 1) if $v_1=0$, then $v'_1=1$; 2) if $v_i=1$ and $v_{i+1}=0$ for some $i$ where $0$, then $v'_i=0$ and $v'_{i+1}=1$; 3) if $v_i=1$ for some $i$ where $s$, then $v'_i=0$; 4) if $v_s=1$ and $v_i=0$ for all $i$ where $s$, then $v'_s=0$ and $v'_i=1$ for all $i$, $s$; 5) there are no other differences between $v$ and $\gamma(v)$. A formula for counting the number of inaccessible states in the considered dynamic systems is proposed. The table with the number of inaccessible states in systems $(B^{8+c},\gamma)$ for $1$ is given.

Détail

Keywords: finite dynamic system, inaccessible state, palm, starlike tree.