Geodesic
Number of inaccessible states in finite dynamic systems of binary vectors associated with palms orientations
Prikladnaâ diskretnaâ matematika, no. 3 (2015), pp. 63-73.

Voir la notice de l'article provenant de la source Math-Net.Ru

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 $\gamma$ transforms the given palm orientations by reversing all arcs that enter into sinks. The following formula for the number of inaccessible states in the considered dynamic systems is proved: $2^{s+c}-2^s-2^{s-3}+\Omega(-1)-2\Omega(1)+\Omega(3)$, where $\Omega(x)=\sum_{i = 1}^{\left[(s - x)/4\right]}(-1)^{i+1}\cdot2^{s-x-4i}\cdot C^i_{s-x-3i}$. As a corollary, the number of accessible states equals $2^s+2^{s-3}-\Omega(-1)+2\Omega(1)-\Omega(3)$. The corresponding statistical tables for systems with different parameters $s$ and $c$ are given.
Keywords: finite dynamic system, inaccessible state, palm, starlike tree. 
@article{PDM_2015_3_a4,
     author = {A. V. Zharkova},
     title = {Number of inaccessible states in finite dynamic systems of binary vectors associated with palms orientations},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {63--73},
     publisher = {mathdoc},
     number = {3},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2015_3_a4/}
}
TY  - JOUR
AU  - A. V. Zharkova
TI  - Number of inaccessible states in finite dynamic systems of binary vectors associated with palms orientations
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2015
SP  - 63
EP  - 73
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2015_3_a4/
LA  - ru
ID  - PDM_2015_3_a4
ER  - 
%0 Journal Article
%A A. V. Zharkova
%T Number of inaccessible states in finite dynamic systems of binary vectors associated with palms orientations
%J Prikladnaâ diskretnaâ matematika
%D 2015
%P 63-73
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2015_3_a4/
%G ru
%F PDM_2015_3_a4
A. V. Zharkova. Number of inaccessible states in finite dynamic systems of binary vectors associated with palms orientations. Prikladnaâ diskretnaâ matematika, no. 3 (2015), pp. 63-73. http://geodesic.mathdoc.fr/item/PDM_2015_3_a4/

[1] Hayes J. P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., C25:9 (1976), 875–884 | DOI | MR | Zbl

[2] Abrosimov M. B., Graph Models for Fault-Tolerance, SSU Publ., Saratov, 2012, 192 pp. (in Russian)

[3] Kurnosova S. G., “T-irreducible extensions of some classes of graphs”, Teoreticheskie problemy informatiki i ee prilozheniy, 2004, no. 6, 113–125 (in Russian)

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

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

[6] Salii V. N., “On a class of finite dynamic systems”, Vestnik Tomskogo gosudarstvennogo universiteta. Prilozhenie, 2005, no. 14, 23–26 (in Russian)

[7] Vlasova A. V., The study of evolutionary parameters in dynamic systems of binary vectors, Certificate of state registration of the computer program No. 2009614409, 20 august 2009 (in Russian)

[8] Zharkova A. V., “Attractors in finite dynamic systems of binary vectors associated with palms orientations”, Prikladnaya diskretnaya matematika, 2014, no. 3(25), 58–67 (in Russian)

[9] Zharkova A. V., “Inaccessible states in dynamic systems associated with paths and cycles”, Izv. Sarat. un-ta. Nov. ser. Ser. Matematika. Mekhanika. Informatika, 11:4 (2011), 116–123 (in Russian)

[10] Vlasova A. V., “Dynamic systems defined by palm trees”, Komp'yuternye nauki i informatsionnye tekhnologii, Materialy Mezhdunar. nauch. konf., SSU Publ., Saratov, 2009, 57–60 (in Russian)

[11] Sequence A135491, The online encyclopedia of integer sequences, , Date use: 04.08.2015 https://oeis.org/A135491

[12] Coin tossing, Wolfram MathWorld: the web's most extensive mathematical resource, , Date use: 04.08.2015. http://mathworld.wolfram.com/CoinTossing.html