Zero-forcing Finite Automata

Subject Areas : International Journal of Industrial Mathematics

مرضیه شمسی زاده ¹ , محمد مهدی زاهدی ² , معصومه گلمحمدیان ³ , خدیجه ابول پور ⁴

1 - Department of Mathematics, Behbahan Khatam Alanbia University of Technology, Behbahan, Iran.
2 - Department of Mathematics, Graduate University of Advanced Technology, Kerman, Iran.
3 - Department of Mathematics, Tarbiat Modares University, Tehran, Iran
4 - Department of Mathematics, Shiraz Branch, Islamic Azad University, Shiraz, Iran

Received: 2021-02-13 Accepted : 2021-08-01 Published : 2021-10-01

Keywords: Graph, Zero forcing set, Language of automata, automata, graph automata,

Abstract :

The current study aims to establish a connection between graphs and automata theory, which apparently demonstrate different mathematical structures. Through searching out some properties of one of these structures, we try to find some new properties of the other structure as well. This will result in obtaining some unknown properties. At first, a novel automaton called zero-forcing (Z-F) finite automata is defined according to the notion of a zero-forcing set of a graph. It is shown that for a given graph and for some zero forcing sets, various Z-F-finite automata will be obtained. In addition, the language and the closure properties of Z-F-finite automata, in particular; union, connection, and serial connection are studied. Moreover, considering some properties of graphs such as the closed trail, connected and complete; some new features for Z-F-finite automata are presented. Further, it is shown that there is not any finite graph such that f be a part of the language of its Z-F-finite automata. Actually, it is proved that for every given graph, the Z-F-finite automata of it does not show any closed trail containing all edges for every zero forcing set, but if the graph G has been a closed trail containing all edges, then the Z-F-finite automata of it has a weak closed trail containing all edges. Some examples are also given to clarify these new notions.

References:

[1] L. Aceto, A. Ingolfsdottir, K. G. Larsen, J. I. Srba, Reactive systems: modelling, specifcation and verifcation, Cambridge University Press, 2007.
[2] AIM Minimum Rank-Special Graphs Work Group (F. Barioli, W. Barrett, S. Butler, S. M. Cioaba, D. Cvetkovic, S. M. Fallat, C. Godsil, W. Haemers, L. Hogben, R. Mikkelson, S. Narayan, O. Pryporova, I. Sciriha, W. So, D. Stevanovic, H. van der Holst, K. Vander Meulen, A. Wangsness), Zero forcing sets and the minimum rank of graphs, Linear Algebra and its Applications 428 (2008) 1628-1648.
[3] E. Almodovar, L. DeLoss, L. Hogben, K. Hogenson, K. Myrphy, T. Peters, C. Ramrez, C. Minimum rank, Maximum nullity and zero forcing number, and spreads of these parameters for selected graph families, Involve, A Journal of Mathematics 3 (2010) 371-392.
[4] M. A. Arbib, Y. Give’on, Algebra automata I: Parallel programming as a prolegomena to the categorical approach, Information and Control 12 (1968) 331-345.
[5] F. Barioli, W. Barrett, S. Fallat, H. T. Hall, L. Hogben, B. Shader, P. van den Driessche, H. van der Holst, Parameters related to treewidth, zero forcing, and maximum nullity of a graph, Journal of Graph Theory 72 (2013) 146-177.
[6] D. Burgarth, D. D’Alessandro, L. Hogben, S. Severini, M. Young. Zero forcing, Linear and quantum controllability for systems evolving on networks, IEEE Transactions in Automatic Control 58 (2013) 2349-2354.
[7] D. Burgarth, V. Giovannetti, Full control by locally induced relaxation, Physical Review Letters 99 (2007) 100-501.
[8] D. Burgarth, K. Maruyama, Indirect Hamiltonian identification through a small gateway, New Journal of Physics 11 (2009) 103-019.
[9] C. G. Cassandras, S. Lafortune, Introduction to discrete event systems, Springer Science & Business Media, 2009.
[10] J. Cerny, Poznamka k homogenym, Experimentom s konecinymi automatami,

Matematicko-fyzikln 208-215.

fakulta

14

(1964)

[11] A. Dovier, C. Piazza, A. Policriti, An efficient algorithm for computing bisimulation equivalence, Theoretical Computer Science 311 (2004) 221-256.
[12] C. J. Edholm, L. Hogben, M. Huynh, J. Lagrange, D. D. Row, Vertex and edge spread of zero forcing number, maximum nullity, and minimum rank of a graph, Linear Algebra and its Applications 436 (2012) 4352-4372.
[13] H. Ehrig, G. Rozenberg, HJ Kreowski, Handbook of graph grammars and computing by graph transformation, World Scientific, 1999.
[14] S. Even, On information lossless automata of finite order, IEEE Transactions on Electronic Computers 14 (1965) 561-569.
[15] L. H. Huang, G. J. Chang, H. G. Yeh, On minimum rank and zero forcing sets of a graph, Linear Algebra and its Applications 432 (2010) 2961-2973.
[16] S. C. Kleene, Representation of events in nerve nets and finite automata, Automata Studies, Princeton University Press, Princeton, N.J. 6 (1956) 3-41.
[17] D. S. Malik, J. N. Mordeson, Fuzzy automata and languages: Theory and Applications, Chapman Hall, CRC Boca Raton, London, New York, Washington DC, 2002.
[18] M. Roggenbach, M. Majster-Cederbaum, Towards a unified view of bisimulation: a comparative study, Theoretical Computer Science 238 (2000) 81-130.
[19] D. Row, A technique for computing the zero forcing number of a graph with a cutvertex, Linear Algebra and its Applications 436 (2012) 4423-4432.
[20] S. Severini, Nondiscriminatory propagation on trees, Journal of Physics A 41 (2008) 482-502.
[21] M. Shamsizadeh, M. M. Zahedi, Bisimulation of type 2 for BL-general fuzzy automata, Soft Computing 23 (2019) 9843-9852.
[22] M. Shamsizadeh, M. M. Zahedi, Kh. Abolpour, Bisimulation for BL-general fuzzy automata, Iranian Journal of Fuzzy Systems 13 (2016) 35-50.
[23] M. Shamsizadeh, M. M. Zahedi, Kh. Abolpour, Reduction of BL-general L-fuzzy automata, Iranian Journal of Mathematical Sciences 2020.
[24] P. H. Starke, Abstrakte Automaten, VEB

Deutscher Berlin, 1969.

Verlag

der

Wissenschaften,

[25] D. B. West, Introduction to graph theory, Upper Saddle River: Prentice hall (2001).