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.

Bibliographie

[1] Vlasova A. V., Issledovanie evolyutsionnykh parametrov v dinamicheskikh sistemakh dvoichnykh vektorov, Svid. o gos. registratsii programmy dlya EVM No 2009614409, vydannoe Rospatentom. Zaregistrirovano v Reestre programm dlya EVM 20 avgusta 2009 g.

[2] Zharkova A. V., “O vetvlenii i neposredstvennykh predshestvennikakh sostoyanii v konechnoi dinamicheskoi sisteme vsekh vozmozhnykh orientatsii grafa”, Prikladnaya diskretnaya matematika. Prilozhenie, 2013, no. 6, 76–78

[3] Zharkova A. V., “Nedostizhimye sostoyaniya v dinamicheskikh sistemakh, assotsiirovannykh s tsepyami i tsiklami”, Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika, 11:4 (2011), 116–123

[4] Salii V. N., “Ob odnom klasse konechnykh dinamicheskikh sistem”, Vestnik Tomskogo gosudarstvennogo universiteta. Prilozhenie, 2005, no. 14, 23–26

[5] Barbosa V. C., An Atlas of Edge-reversal Dynamics, Chapman Hall/CRC, Boca Raton, 2001, 385 pp. | MR | Zbl

[6] Vlasova A. V., “Dinamicheskie sistemy, opredelyaemye palmami”, Kompyuternye nauki i informatsionnye tekhnologii, Materialy Mezhdunar. nauch. konf., Izd-vo Sarat. un-ta, Saratov, 2009, 57–60