SH-graph automata with applications

Document Type : Research Paper

Authors

1 School of Science, XI'an Polytechnic University, Shaanxi, China

2 Business School, Xi'an International University, Shaanxi, China

3 Department of Mathematics, Kerman Graduate University of Advanced Technology, Kerman, Iran

Abstract

In this paper, because semihoops are the most basic residuated structure that contain all logical algebras based on Galois connections, therefore we introduce a new type fuzzy graph and its complement based on semihoops, denoted by $SH$-graph $G$ and $G^\prime$, respectively. Then, the $SH$-graph automata related to the $SH$-graph $G$ and a minimum zero forcing set are introduced, denoted by $A(Z(G))$. After that, the concepts of isomorphism between two $SH$-graphs $G_1$ and $G_2$ and isomorphism between two $SH$-graph automata $A(Z(G_1))$ and $A(Z(G_2))$ are introduced. Then, we prove that if two $SH$-graphs $G_1$ and $G_2$ are isomorphic, then two $SH$-graph automata $A(Z(G_1))$ and $A(Z(G_2))$ are isomorphic; otherwise it is not true. In addition, the concept of equivalence of $SH$-graph automata is proposed. Moreover, we prove that $SH$-graph automata obtained from the same $SH$-graphs are equivalent under different zero forcing sets in some special $SH$-graphs. And then, we know that $SH$-graph automata $A(Z(G_1))$ and $A(Z(G_2))$ are equivalent can not be characterized by $SH$-graphs $G_1$ and $G_2$ being isomorphic. Finally, we introduce a several of simple practical applications of $SH$-graph and $SH$-graph automata.

Keywords

Main Subjects

References

[1] AIM Minimum Rank Special Graphs Work Group. (2008). Zero forcing sets and the minimum rank of graphs. Linear Algebra and its Applications, 428(7), 1628{1648. https://doi.org/10.1016/j.laa.2007.10.009
[2] Arenas, A., Daz-Guilera, A., Kurths, J., Moreno, Y., & Zhou, C. (2008). Synchronization in complex networks. Physics Reports, 469(3), 93-153. https://doi.org/10.1016/j.physrep.2008.09.002
[3] Borzooei, R. A., & Kologani, M. A. (2015). Local and perfect semihoops. Journal of Intelligent & Fuzzy Systems, 29(1), 223-234. https://doi.org/10.3233/IFS-151589
[4] Ciric, M., & Bogdanovic, S. (1999). Lattices of subautomata and direct sum decompositions of automata. In Algebra Colloquium, 6, 71-88.
[5] Ciric, M., & Ignjatovic, J. (2008). Algebraic theory of lattice-valued fuzzy languages and automata. LINZ, 19.
[6] Deng, W., & Qiu, D. (2014). Supervisory control of fuzzy discrete-event systems for simulation equivalence. IEEE Transactions on Fuzzy Systems, 23(1), 178-192. https://doi.org/10.1109/tfuzz.2014.2310466
[7] Esteva, F., Godo, L., Hajek, P., & Montagna, F. (2003). Hoops and fuzzy logic. Journal of Logic and Computation, 13(4), 532-555. https://doi.org/10.1093/logcom/13.4.532
[8] Granovetter, M. (1978). Threshold models of collective behavior. American journal of sociology, 83(6), 1420-1443. https://doi.org/10.1086/226707
[9] Ignjatovic, J., Ciric, M., & Bogdanovic, S. (2008). Determinization of fuzzy automata with membership values in complete residuated lattices. Information Sciences, 178(1), 164-180. https://doi.org/10.1016/j.ins.2007.08.003
[10] Kaufmann, A. (1973). Introduction a la theorie des sous-ensembles ous a l'usage des ingenieurs (fuzzy sets theory), 3. Masson. https://doi.org/10.3406/ecoap.1976.4182
[11] Kempe, D., Kleinberg, J., & Tardos, E. (2003). Maximizing the spread of in uence through a social network. In  roceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 137-146.
https://doi.org/10.1145/956750.956769
[12] Mordeson, J. N., & Malik, D. S. (2002). Fuzzy automata and languages: theory and applications. Chapman and Hall/CRC. https://doi.org/10.1201/9781420035643
[13] Qiu, D. (2001). Automata theory based on complete residuated lattice-valued logic. Science in China Series: Information Sciences, 44(6), 419-429. https://doi.org/10.1007/bf02713945
[14] Qiu, D. (2002). Automata theory based on complete residuated lattice-valued logic (II). Science in China Series F: Information Sciences, 45(6), 442-452. https://doi.org/10.1360/02yf9038
[15] Qiu, D. (2004). Characterizations of fuzzy  nite automata. Fuzzy sets and systems, 141(3), 391-414. https://doi.org/10.1016/s0165-0114(03)00202-1
[16] Qiu, D. (2006). Pumping lemma in automata theory based on complete residuated lattice-valued logic: a note. Fuzzy Sets and Systems, 157(15), 2128-2138. https://doi.org/10.1016/j.fss.2006.03.014
[17] Qiu, D. (2007). A note on Trillas' CHC models. Arti cial intelligence, 171(4), 239-254. https://doi.org/10.1016/j.artint.2006.12.002
[18] Qiu, D. (2005). Supervisory control of fuzzy discrete event systems: A formal approach. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 35(1), 72-88. https://doi.org/10.1109/tsmcb.2004.840457
[19] Qiu, D., & Liu, F. (2008). Fuzzy discrete-event systems under fuzzy observability and a test algorithm. IEEE Transactions on Fuzzy Systems, 17(3), 578-589. https://doi.org/10.1109/tfuzz.2008.924212
[20] Raisi Sarbizhan, E., Mehdi Zahedi, M., & Shamsizadeh, M. (2023). L-graph automata and some applications. The Computer Journal, 66(7), 1698-1716. https://doi.org/10.1093/comjnl/bxac035
[21] Rosenfeld, A. (1971). Fuzzy groups. Journal of mathematical analysis and applications, 35(3), 512-517. https://doi.org/10.1016/0022-247x(71)90199-5
[22] Santos, E. S. (1968). Maximin automata. Information and Control, 13(4), 363-377. https://doi.org/10.1016/s0019-9958(68)90864-4
[23] Shamsizadeh, M., Zahedi, M. M., Golmohamadian, M., & Abolpour, K. H. (2021). Zero-forcing  nite automata. International Journal of Industrial Mathematics, 13(4), 477-488. https://ijim.srbiau.ac.ir/article-18196
[24] Tiwari, S. P., & Sharan, S. (2012). Fuzzy automata based on lattice-ordered monoid with algebraic and topological aspects. Fuzzy information and engineering, 4(2), 155-164. https://doi.org/10.1007/s12543-012-0108-y
[25] Wang, Z. Y., Xin, X. L., & Yang, X. F. (2024). L-fuzzy ideal theory on bounded semi-hoops. Italian Journal of Pure and Applied Mathematics, 51, 472-495.
[26] Wee, W. G. (1967). On generalizations of adaptive algorithms and application of the fuzzy sets concept to pattern classi cation. Purdue University.
[27] West, D. B. (2001). Introduction to graph theory. Upper Saddle River: Prentice hall.
[28] Zadeh, L. A. (1971). Similarity relations and fuzzy orderings. Information sciences, 3(2), 177-200. https://doi.org/10.1016/s0020-0255(71)80005-1 

Files

History

  • Receive Date: 20 November 2025
  • Revise Date: 30 January 2026
  • Accept Date: 09 May 2026

Share

How to cite

Statistics