On Some Control-theoretic And Dynamical Problems Of Logical Dynamical Systems

Boolean networks(BNs)are finite-state networks consisting of finite nodes,while cellular automata(CAs)are uniform finite-state networks consisting of countably infinitely many nodes.The former,proposed by Kauffman in 1969,is an effective model describing biological systems,such as genetic regulatory networks,and is a focus both in the fields of biology and systems science.The latter,proposed by Ulam and Von Neumann in1940 s,was constructed to simulate self-replication in biology at first,and has important applications in theoretical computer science,cryptography,etc..This thesis surveys the author’s works on control-theoretic problems of BNs and dynamical properties of CAs during the period of pursing his doctorate.1.Observability is one of the fundamental control-theoretic problems.The concept of observability of Boolean control networks(BCNs,i.e.,BNs with external variables)was proposed by Prof.Daizhan Cheng and Dr.Hongsheng Qi in 2009 for the first time.And how to determine this observability is solved for the first time in this thesis.Due to the nonlinearity of BCNs,four observability were proposed.In this thesis,a new observability is proposed to unify these four observability.This thesis proposes a unified approach based on the theories of finite automata and formal languages to solve how to determine all these observability.Using these results,the implication relationships between these observability are also obtained and it is proved that no two of the these observability are equivalent.Lastly,algorithms for determining the initial state are designed.2.Invertibility is a classical control-theoretic problem.There had been no result on the invertibility of BCNs before this thesis came up.This paper gives formal definitions of invertibility and a more general concept — nonsingularity for BCNs for the first time.Using the theory of symbolic dynamics,how to determine invertibility is solved.A new concept of nonsingularity weighted pair graph is proposed to solve how to determine nonsingularity.The relationship between invertibility and the solvability of the identification problem is also investigated.Lastly,the core network regulating the mammalian cell cycle is investigated to reveal the biological meanings of invertibility.3.In genetic regulatory networks,the asynchrony of the transportation of RNA and proteins will result in the time delay phenomenon especially in eukaryotes.Hence studying BCNs with time delays is of theoretical and practical importance.New concepts of constructed forest,controllability constructed path and observability constructed path are proposed.Based on these new concepts,an equivalent testing criterion for the controllability and a sufficient condition for the observability of BCNs with not necessarily bounded time delays are given.The concepts of constructed forest and controllability constructed path are extended to probabilistic cases.Some necessary conditions and sufficient conditions for the controllability of probabilistic BCNs with not necessarily bounded time delays are given.Besides,the essential differences between the deterministic case and the probabilistic case are revealed.4.An equivalent algebraic characterization for the reversibility of a CA on its limit set and a concept of generalized inverse CA are proposed.It is proved that a CA is reversible on its limit set if and only if it has a generalized inverse CA;it is algorithmically undecidable whether a given CA has a generalized inverse CA;and if a CA has a generalized inverse CA,they have the same topological entropy.At last,using the semi-tensor product of matrices,an algorithm for calculating the generlized inverse CAs for CAs with periodic boundary conditions is given.5.Two classes of Devaney-chaotic reversible CAs are given.The first class have nonempty and nondense sets of strictly temporally periodic points,and the second class have dense sets of strictly temporally periodic points.These results give a positive answer and a negative answer to the open problems proposed in the 19 th International Workshop on Cellular Automata and Discrete Complex Systems: “Does there exist a surjective CA whose set of strictly temporally periodic points is neither empty nor dense?” and“Are chaotic CAs precisely those surjective CAs that have no strictly temporally periodic points?”,respectively.