SCIENTIA SINICA Informationis, Volume 46 , Issue 2 : 228-243(2016) https://doi.org/10.1360/N112015-00154-93

Shortcuts and periodicity of networked max-plus system with ring topology

More info
  • AcceptedAug 21, 2015
  • PublishedJan 28, 2016


This paper investigates the characteristics of cyclicity and cycle time after adding shortcuts to the networked max-plus system with ring topology. Both the lower bound expression of the probability of cyclicity being one and the sufficient and necessary condition for the cycle time being unchanged are established after adding k shortcuts with the same starting point. For two systems with the dimensions of a prime number and its power, it is discovered that the lower bounds of the probability of cyclicity being one is consistent after adding the shortcuts. The paper also investigates some situations of adding shortcuts under conditions with different starting points. The lower bound expression of the probability of cyclicity being one is given after adding k shortcuts with mutual disjoint. The method for algebra and combinatorics is constructive. The algorithm of the cycle time remaining unchanged is given after adding k shortcuts with the same starting point. It is proven that such algorithm has a polynomial bound. At the same time, the numerical example for cyclicity is also given.


[1] Wang X F, Chen G R. Synchronizaion in small-world dynamical networks. Int J Bifurcation Chaos, 2002, 12:187-192. Google Scholar

[2] Liu Z X, Guo L. Connectivity and synchronzation of the Vicsek's model. Sci China Ser F-Inf Sci, 2008, 51:848-858. Google Scholar

[3] Hui Q, Haddad W M. Distributed nonlinear control algorithms for network consensus. Automatica, 2008, 44:2375-2381. Google Scholar

[4] Shi H, Wang L, Chu T G. Flocking of mult-agent systems with a dynamic virtual leader. Int J Control, 2009, 82:43-58. Google Scholar

[5] Hokayem P, Chatterjee D, Ramponi F A, et al. Stable networked control systems with bounded control authority. IEEE Trans Autom Control, 2012, 57:3153-3157. Google Scholar

[6] Lee P, Clark A, Bushnell L, et al. A passivity framework for modeling and mitigating wormhole attacks on networked control systems. IEEE Trans Autom Control, 2014, 59:3224-3227. Google Scholar

[7] Razeghi-Jahromi M, Seyedi A. Stabilization of networked control systems with sparse observer-controller networks. IEEE Trans Autom Control, 2015, 60:1686-1691. Google Scholar

[8] Wang W, Ne si c D, Postoyan R. Emulation-based stabilization of networked control systems implemented on FlexRay. Automatica, 2015, 59:73-83. Google Scholar

[9] Zhao Q C. Analysis of impacts of adding shortcuts to DEDS of ring topology. J Syst Sci Math Sci, 2011, 31:1092-1096[赵千川. 添加捷径对环状DEDS 的影响分析. 系统科学与数学, 2011, 31:1092-1096]. Google Scholar

[10] Addad B, Amari S, Lesage J J. Networked con icting timed event graphs representation in (Max, +) algebra. Discrete Event Dynamic Syst Theory Appl, 2012, 22:429-449. Google Scholar

[11] Cuninghame-Green R A. Minimax algebra. In:Lecture Notes in Economics and Mathematical Systems. Berlin:Springer, 1979. Google Scholar

[12] Cohen G, Dubois D, Quadrat J-P, et al. A linear-system-theoretic view of discrete event processes and its use for performance evaluation in manufacturing. IEEE Trans Autom Control, 1985, 30:210-220. Google Scholar

[13] Baccelli F, Cohen G, Olsder G J, et al. Synchronization and Linearity. New York:Wiley, 1992. Google Scholar

[14] Heidergott B, Olsder G J, van der Woude J. Max Plus at Work:Modeling and Analysis of Synchronized Systems. Princeton:Princeton University Press, 2006. Google Scholar

[15] Wang L, Zheng D Z. On the reachability of linear discrete event dynamic systems. Appl Math J Chinese Univ, 1990, 5:292-301[王龙, 郑大钟. 线性离散事件动态系统的可达性. 高等学校应用数学学报, 1990, 5:292-301]. Google Scholar

[16] Zhang M,Wu Z. Controllability and observability problems in linear discrete event system model of FMS. In:Workshop on Discrete Event System Theory and Applications in Manufacturing and Social Phenomena. Beijing:International Academic Publishers, 1991. 267-270. Google Scholar

[17] Chen W D, Qi X D. Period assignment of discrete event dynamic systems. Sci Sin Math, 1993, 23:1-7[陈文德, 齐向东. 离散事件动态系统的周期配置. 中国科学A 辑, 1993, 23:1-7]. Google Scholar

[18] Chen W, Qi X, Deng S. The eigen-problem and period analysis of the discrete event system. Syst Sci Math Sci, 1990, 3:243-260. Google Scholar

[19] Gaubert S. Th eorie des Syst emes Lin eaires dans les Dioides (in French). Dissertation for Ph.D. Degree. Paris:L'Ecole Nationale Sup erieure des Mines de Paris, 1992. Google Scholar

[20] Gunawardena J. From max-plus algebra to nonexpansive mappings:a nonlinear theory for discrete event systems. Theor Comput Sci, 2003, 293:141-167. Google Scholar

[21] Gaubert S, Gunawardena J. The duality theorem for min-max functions. Comptes Rendus Acad emie des Sci Paris, 1998, 326:43-48. Google Scholar

[22] Zhao Q. A remark on inseparability of min-max systems. IEEE Trans Autom Control, 2004, 14:967-970. Google Scholar

[23] Necoara I, de Schutter B, van den Boom T J J, et al. Robust control of constrained max-plus-linear systems. Int J Robust Nonlinear Control, 2009, 19:218-242. Google Scholar

[24] van den Boom T J J, de Schutter B. Modeling and control of switching max-plus-linear systems with random and deterministic switching. Disc Event Dynamic Syst Theory Appl, 2012, 22:293-332. Google Scholar

[25] Apostol T M. Introduction to Analytic Number Theory. Berlin:Springer, 1976. Google Scholar

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号