×

A weighted pair graph representation for reconstructibility of Boolean control networks. (English) Zbl 1350.93048

Summary: A new concept of Weighted Pair Graphs (WPGs) is proposed to represent a new reconstructibility definition for Boolean Control Networks (BCNs), which is a generalization of the reconstructibility definition given in definition 4 in E. Fornasini, M. Valcher [IEEE Trans. Automat. Control, 58, pp. 1390–1401, (2013)]. Based on the WPG representation, an effective algorithm for determining the new reconstructibility notion for BCNs is designed with the help of the theories of finite automata and formal languages. We prove that a BCN is not reconstructible iff its WPG has a complete subgraph. In addition, we prove that a BCN is reconstructible in the sense of definition 4 in [loc. cit.] iff its WPG has no cycles, which is simpler to check than the condition in Theorem 4 in [loc. cit.].

MSC:

93C30 Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems)
68Q45 Formal languages and automata
94C15 Applications of graph theory to circuits and networks
92B99 Mathematical biology in general
68Q80 Cellular automata (computational aspects)

Software:

UMDES
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] J. Kari, {\it A Lecture Note on Automata and Formal Languages}, (2016).
[2] P. Linz, {\it An Introduction to Formal Languages and Automata}, Jones and Bartlett, Sudbury, MA, 2013. · Zbl 1230.68010
[3] T. Ideker, T. Galitski, and L. Hood, {\it A new approach to decoding life: systems biology}, Annu. Rev. Genomics Hum. Genet., 2 (2001), pp. 343-372.
[4] H. Kitano, {\it Systems biology: A brief overview}, Sceince, 259 (2002), pp. 1662-1664.
[5] S. A. Kauffman, {\it Metabolic stability and epigenesis in randomly constructed genetic nets}, J. Theoret. Biol., 22 (1969), pp. 437-467.
[6] T. Akutsu, S. Miyano, and S. Kuhara,{\it Inferring qualitative relations in genetic networks and metabolic pathways}, Bioinformatics, 16 (2000), pp. 727-734.
[7] R. Albert and A.-L. Barabasi, {\it Dynamics of complex systems: Scaling laws or the period of Boolean networks}, Phys. Rev. Lett., 84 (2000), pp. 5660-5663.
[8] D. Laschov and M. Margaliot, {\it Minimum-time control of Boolean networks}, SIAM J. Control Optim.,51 (2013), pp. 2869-2892. · Zbl 1276.49013
[9] K. Zhang, L. Zhang, and L. Xie, {\it Invertibility and nonsingularity of Boolean control networks}, Automatica, 60 (2015), pp. 155-164. · Zbl 1331.93106
[10] T. Akutsu, M. Hayashida, W. Ching, and M. K. Ng, {\it Control of Boolean networks: Hardness results and algorithms for tree structured networks}, J. Theoret. Biol., 244 (2007), pp. 670-679. · Zbl 1450.92040
[11] D. Cheng and H. Qi, {\it A linear representation of dynamics of Boolean networks}, IEEE Trans. Automat. Control, 55 (2010), pp. 2251-2258. · Zbl 1368.37025
[12] D. Cheng and H. Qi, {\it Controllability and observability of Boolean control networks}, Automatica, 45 (2009), pp. 1659-1667. · Zbl 1184.93014
[13] Y. Zhao, H. Qi, and D. Cheng, {\it Input-state incidence matrix of Boolean control networks and its applications}, Systems Control Lett., 59 (2010), pp.767-774. · Zbl 1217.93026
[14] R. Li, M. Yang, and T. Chu, {\it Controllability and observability of Boolean networks arising from biology}, Chaos, 25 (2015), pp. 1-15. · Zbl 1345.92063
[15] D. Cheng, H. Qi, T. Liu, and Y. Wang, {\it A note on observability of Boolean control networks}, Systems Control Lett., 87 (2016), pp. 76-82. · Zbl 1327.93094
[16] D. Cheng and Y. Zhao, {\it Identification of Boolean control networks}, Automatica, 47 (2011), pp. 702-710. · Zbl 1215.93035
[17] D. Laschov, M. Margaliot, and G. Even,{\it Observability of Boolean networks: A graph-theoretic approach}, Automatica, 49 (2013), pp. 2351-2362. · Zbl 1364.93095
[18] \scE. Fornasini and M. Valcher, {\it Observability, reconstructibility and state observers of Boolean control networks}, IEEE Trans. Automat. Control, 58 (2013), pp. 1390-1401. · Zbl 1369.93101
[19] E. Fornasini and M. Valcher, {\it Fault detection analysis of Boolean control networks}, IEEE Trans. Automat. Control, 60 (2015), pp. 2734-2739. · Zbl 1360.94491
[20] R. Li, M. Yang, and T. Chu, {\it Observability conditions of Boolean control networks}, Internat. J. Robust Nonlinear Control, 24 (2013), pp. 2711-1723. · Zbl 1305.93038
[21] D. Cheng, H. Qi, and Z. Li, {\it Analysis and Control of Boolean Networks: A Semi-Tensor Product Approach,} Springer, London, 2011. · Zbl 1209.93001
[22] K. Zhang and L. Zhang, {\it Observability of Boolean control networks: A unified approach based on the theories of finite automata and formal languages}, in Proceedings of the 33rd Chinese Control Conference, Nanjing, China, 2014, pp. 6854-6861.
[23] \scK. Zhang, L. Zhang, and L. Xie, {\it Finite automata approach to observability of switched Boolean control networks}, Nonlinear Anal. Hybrid Syst., 19 (2016), pp. 186-197. · Zbl 1343.93021
[24] S. Shu, F. Lin, and H. Ying, {\it Detectability of discrete event systems}, IEEE Trans. Automat. Control, 52 (2007), pp.2356-2359. · Zbl 1366.93366
[25] P. Ramadge and W. Wonham, {\it Supervisory control of a class of discrete event processess}, SIAM J. Control Optim., 25 (1987), pp. 206-230. · Zbl 0618.93033
[26] C. G. Cassandras and S. Lafortune, {\it Introduction to Discrete Event Systems}, Springer, New York, 2008. · Zbl 1165.93001
[27] F. Lin and W. Wonham, {\it On observability of discrete-event systems}, Inform. Sci., 44 (1988), pp. 173-198. · Zbl 0644.93008
[28] W. Wonham, {\it Towards an abstract internal model principle}, IEEE Trans. Syst. Man Cybern., 6 (1976), pp. 735-740. · Zbl 0341.93003
[29] F. Lin, {\it Control of networked discrete event systems: Dealing with communication delays and losses}, SIAM J. Control Optim., 52 (2014), pp. 1276-1298. · Zbl 1292.93083
[30] W. Wonham, {\it Supervisory Control of Discrete-Event Systems}, Lecture notes, (2014). · Zbl 0679.68042
[31] R. Su and G. Woeginger, {\it String execution time for finite languages: Max is easy, min is hard}, Automatica, 47 (2011), pp. 2326-2329. · Zbl 1228.93005
[32] S. Even and G. Even, \itGraph Algorithms, 2nd ed., Cambridge University Press, New York, 2012. · Zbl 1237.05199
[33] S. Sridharan, R. Layek, A. Datta, and J. Venkatraj, {\it Boolean modeling and fault diagnosis in oxidative stress response}, BMC Genomics, 13 (2012), pp. 1-16.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.