اتوماتای متناهی صفر تحمیلی

Subject Areas : International Journal of Industrial Mathematics

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

1 - گروه ریاضی، دانشگاه صنعتی خاتم الانبیاء بهبهان، بهبهان، ایران.
2 - گروه ریاضی، دانشگاه تحصیلات تکمیلی صنعتی و فناوری پیشرفته کرمان، کرمان، ایران.
3 - گروه ریاضی، دانشگاه تربیت مدرس، تهران، ایران.
4 - گروه ریاضی، واحد شیراز، دانشگاه آزاد اسلامی، شیراز، ایران.

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

Keywords: اتوماتاف, گراف, زبان اتوماتا, مجموعه صفر تحمیلی, اتوماتا گراف,

Abstract :

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

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