Zero-forcing Finite Automata

محورهای موضوعی : مجله بین المللی ریاضیات صنعتی

M. Shamsizadeh ¹ , M. M. Zahedi ² , M. Golmohamadian ³ , KH. Abolpour ⁴

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

تاریخ دریافت : 1399/11/25 تاریخ پذیرش : 1400/05/10 تاریخ انتشار : 1400/07/09

کلید واژه: Graph, Zero forcing set, Language of automata, automata, graph automata,

چکیده مقاله :

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.

چکیده انگلیسی:

هدف از مطالعه حاضر برقراری ارتباط بین گراف ها و تئوری اتوماتاست که ساختارهای مختلف ریاضی را نشان می دهد. از طریق بررسی برخی از خصوصیات یکی از این ساختارها ، سعی می کنیم برخی از خصوصیات جدید ساختار دیگر را پیدا کنیم. این امر منجر به بدست آوردن برخی خصوصیات ناشناخته خواهد شد. در ابتدا، یک اتوماتای جدید به نام اتوماتای حالت متناهی صفر تحمیلی با توجه به مفهوم مجموعه صفر تحمیلی تعریف می شود. نشان داده شده است که برای یک گراف داده شده, برای برخی مجموعه های صفر تحمیلی، اتوماتای حالت متناهی صفر تحمیلی مختلفی بدست می آید. علاوه بر این، زبان و خصوصیات بستاری اتوماتای حالت متناهی صفر تحمیلی، به ویژه؛ اجتماع, اتصال و اتصال سریالی مورد مطالعه قرار می گیرد. علاوه بر این، با در نظر گرفتن برخی از خصوصیات گرافها مانند مسیر بسته، اتصال و کامل, برخی از ویژگی های جدید برای اتوماتای حالت متناهی صفر تحمیلی ارائه شده است. بعلاوه، نشان داده شده است که هیچ گراف متناهی وجود ندارد که f بخشی از زبان اتوماتای آن باشد. در حقیقت، ثابت شده است که برای هر گراف داده شده، اتوماتای حالت متناهی صفر تحمیلی آن هیچ دنباله بسته حاوی تمام یالها را برای هر مجموعه صفر تحمیلی نشان نمی دهد، اما اگر گراف G یک دنباله بسته باشد که حاوی تمام یال ها باشد، اتوماتای حالت متناهی صفر تحمیلی آن دارای یک مسیر بسته ضعیف است که حاوی تمام یال ها است. برای روشن شدن این مفاهیم جدید چند مثال نیز آورده شده است.

منابع و مأخذ:

[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).