Fixed Points in Generalized Parallel Dynamical System with NAND or NOR Local Functions over Directed Rooted Trees

Abstract

In order to study the exact number and states of fixed points in the generalized dynamical system with NAND or NOR local functions over directed rooted trees, structural analysis and classification discussion methods are applied. The exact results of the fixed points in such dynamical systems are obtained. It is proved that the fixed points in such dynamical systems are completely determined by the loops in the rooted trees. This work provides a relevant advance in the knowledge of discrete dynamical systems which constitute mathematical tools to model simulation processes.

Keywords

generalized parallel dynamical system / directed rooted tree / Boolean function / fixed point

References

[1] TOROCZKAI Z, GUCLU H. Proximity networks and epidemics[J]. Physica A:Statistical Mechanics and Its Applications, 2007, 378(1):68-75.

[2] GUYEUX C. Convergence versus divergence behaviors of asynchronous iterations,and their applications in concrete situations[J]. Mathematical and Computational Applications, 2020, 25(4):69.

[3] CHIASELOTTI G, GENTILE T, OLIVERIO P A. Parallel and sequential dynamics of two discrete models of signed integer partitions[J]. Applied Mathematics and Computation, 2014,232:1249-1261.

[4] DEFANT C. Binary codes and periodic-2 orbits of sequential dynamical systems[J]. Discrete Mathematics and Theoretical Computer Science, 2017, 19(3):10.

[5] DENG A P, GONG X Y, MA H C. Linear dynamical system over finite distributive lattice[J]. Journal of Donghua University (English Edition), 2021, 38(3):264-271.

[6] ETESAMI S R, BAŞAR T. Complexity of equilibrium in competitive diffusion games on social networks[J]. Automatica, 2016,68:100-110.

[7] XIA M, WU Y Z, WANG Z J. Time delay identification in dynamical systems based on interpretable machine learning[J]. Journal of Donghua University (English Edition), 2022, 39(4):332-339.

[8] SHI Q W, SUN J Q, HOU C Y, et al. Advanced functional fiber and smart textile[J]. Advanced Fiber Materials, 2019, 1(1):3-31.

[9] WANG L, PAN R R, ZHOU J, et al. Application progress of machine vision in textile intellectualization[J]. Cotton Textile Technology, 2021, 49(11):9-11. (in Chinese)

[10] LI C, LI J, LI Y F, et al. Fabric defect detection in textile manufacturing:a survey of the state of the art[J]. Security and Communication Networks, 2021,2021:9948808.

[11] HE Z M, PENG Y N. Progress in fabric defect detection based on deep learning[J]. Wool Textile Journal, 2019, 47(8):83-88. (in Chinese)

[12] ZHU R H, XIN B J, DENG N, et al. Review of fabric defect detection based on computer vision[J]. Journal of Donghua University (English Edition), 2023, 40(1):18-26.

[13] LIU Z Y, CHEN N L, WANG J. Yarn quality prediction for small samples based on AdaBoost algorithm[J]. Journal of Donghua University (English Edition), 2023, 40(3):261-266.

[14] KAWACHI A, OGIHARA M, UCHIZAWA K. Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs[J]. Theoretical Computer Science, 2019,762:25-40.

[15] ALEDO J A, DIAZ L G, MARTINEZ S, et al. On the periods of parallel dynamical systems[J]. Complexity, 2017,2017:7209762.

[16] ALEDO J A, DIAZ L G, MARTINEZ S, et al. Maximum number of periodic orbits in parallel dynamical systems[J]. Information Sciences, 2018,468:63-71.

[17] ALEDO J A, BARZANOUNI A, MALEKBALA G, et al. Counting periodic points in parallel graph dynamical systems[J]. Complexity, 2020,2020:9708347.

[18] BARRETT C L, REIDYS C M. Elements of a theory of computer simulation I:sequential CA over random graphs[J]. Applied Mathematics and Computation, 1999, 98(2/3):241-259.

[19] BARRETT C L, MORTVEIT H S, REIDYS C M. Elements of a theory of simulation II:sequential dynamical systems[J]. Applied Mathematics and Computation, 2000, 107(2/3):121-136.

[20] BARRETT C L, MORTVEIT H S, REIDYS C M. Elements of a theory of simulation III:equivalence of SDS[J]. Applied Mathematics and Computation, 2001, 122(3):325-340.

[21] BARRETT C L, MORTVEIT H S, REIDYS C M. ETS IV:sequential dynamical systems:fixed points,invertibility and equivalence[J]. Applied Mathematics and Computation, 2003, 134(1):153-171.

[22] MORTVEIT H S, REIDYS C M. An introduction to sequential dynamical systems[M]. New York: Springer-Verlag, 2008.

[23] ALEDO J A, DIAZ L G, MARTINEZ S, et al. Enumerating periodic orbits in sequential dynamical systems over graphs[J]. Journal of Computational and Applied Mathematics, 2022,405:113084.

[24] ALEDO J A, DIAZ L G, MARTINEZ S, et al. On periods and equilibria of computational sequential systems[J]. Information Sciences, 2017,409/410:27-34.

[25] ALEDO J A, MARTíNEZ S, VALVERDE J C. Parallel dynamical systems over directed dependency graphs[J]. Applied Mathematics and Computation, 2012, 219(3):1114-1119.

[26] ALEDO J A, MARTINEZ S, VALVERDE J C. Parallel dynamical systems over special digraph classes[J]. International Journal of Computer Mathematics, 2013, 90(10):2039-2048.

[27] KOZERENKO S, VALVERDE J C. Periods in XOR parallel dynamical systems over directed dependency graphs[J]. Journal of Computational and Applied Mathematics, 2020,364:112313.

[28] ALEDO J A, BARZANOUNI A, MALEKBALA G, et al. On the periodic structure of parallel dynamical systems on generalized independent Boolean functions[J]. Mathematics, 2020, 8(7):1088.

[29] ALEDO J A, DIAZ L G, MARTINEZ S, et al. Coexistence of periods in parallel and sequential Boolean graph dynamical systems over directed graphs[J]. Mathematics, 2020, 8(10):1812.

[30] ALEDO J A, BARZANOUNI A, MALEKBALA G, et al. Existence,coexistence and uniqueness of fixed points in parallel and sequential dynamical systems over directed graphs[J]. Communications in Nonlinear Science and Numerical Simulation, 2021,103:105966.

[31] ALEDO J A, BARZANOUNI A, MALEKBALA G, et al. Fixed points in generalized parallel and sequential dynamical systems induced by a minterm or maxterm Boolean functions[J]. Journal of Computational and Applied Mathematics, 2022,408:114070.

Funding

2021 Shanghai Philosophy and Social Sciences Planning Project(2021BFX005)