STM Journals Peer-reviewed research from Consortium e-Learning Network

Research & Reviews: Discrete Mathematical Structures Original Research

Semiring-Weighted Automata and Recursive Path Counting for Multi-State Reliability in Discrete Infrastructures

  1. S. Vairachilai School of Computer Science and Artificial Intelligence, SR University, Warangal
  2. Markala Karthik Department of Electrical and Electronics Engineering, SR University, Warangal
  3. Mohammed Almakki School of Engineering, Architecture and Interior Design, Amity University Dubai
  4. Mohammed El Khider Department of General Undergraduate Curriculum Requirements, University of Dubai

Abstract

Multi-state infrastructures such as communication backbones, microgrids, warehouse routing systems, and sensor-actuator pipelines evolve through discrete event sequences rather than through a single binary "working/failed" transition. This paper develops a semiring-weighted automata framework for reliability analysis in which state changes, repair actions, and degraded operating modes are represented by weighted transitions on a finite automaton. A path valuation is defined over an additively idempotent reliability semiring and extended to a hesitation-aware fuzzy semiring so that uncertainty in maintenance quality and observational ambiguity can be included without abandoning discrete rigor. We derive recursive path-counting identities, a transfer-matrix representation, and a closed-form generating function for horizon-limited mission reliability. A min-plus reliability distance is introduced to characterize the least costly restoration sequence, while a max-times acceptance functional captures the best feasible service quality over all admissible event words. We further prove monotonicity, subadditivity, and convergence of a truncated Kleene-star approximation under a contractive spectral condition on the transition operator. Numerical experiments on a five-zone distribution network show that the proposed method separates availability, recoverability, and path diversity more effectively than crisp Markov aggregation.

Keywords

References (24)

  1. Mohri M. Weighted Automata Algorithms. Monographs in Theoretical Computer Science. An EATCS Series. 2009:213-254. doi:10.1007/978-3-642-01492-5_6
  2. Droste M, Kuich W. Semirings and Formal Power Series. Monographs in Theoretical Computer Science. An EATCS Series. 2009:3-28. doi:10.1007/978-3-642-01492-5_1
  3. Mohri M, Pereira F, Riley M. Weighted finite-state transducers in speech recognition. Computer Speech & Language. 2002;16(1):69-88. doi:10.1006/csla.2001.0184
  4. Kostolányi P. Weighted automata and logics meet computational complexity. Information and Computation. 2024;301:105213. doi:10.1016/j.ic.2024.105213
  5. Daviaud L, Johnson M. Feasibility of learning weighted automata on a semiring. Logical Methods in Computer Science. 2025;21(3:15). doi:10.46298/Imcs-21(3:15)2025.
  6. Otero Sánchez Á, Camazón Portela D, López-Ramos JA. On the Solutions of Linear Systems over Additively Idempotent Semirings. Mathematics. 2024;12(18):2904. doi:10.3390/math12182904
  7. Stanimirović PS, Ćirić M, Mourtas SD, Brzaković P, Karabašević D. Simulations and Bisimulations between Weighted Finite Automata Based on Time-Varying Models over Real Numbers. Mathematics. 2024;12(13):2110. doi:10.3390/math12132110
  8. Buchholz P, Kemper P. Model Checking for a Class of Weighted Automata. Discrete Event Dynamic Systems. 2009;20(1):103-137. doi:10.1007/s10626-008-0057-0
  9. Zadeh LA. Fuzzy sets. Information and Control. 1965;8(3):338-353. doi:10.1016/s0019-9958(65)90241-x
  10. Mendel JM. Fuzzy logic systems for engineering: a tutorial. Proceedings of the IEEE. 1995;83(3):345-377. doi:10.1109/5.364485
  11. Yogeesh N, Girija DK, William P, Rashmi M. Improving Speech Privacy with Fuzzy Logic-Based Encryption. 2023 IEEE 2nd International Conference on Industrial Electronics: Developments & Applications (ICIDeA). 2023:217-222. doi:10.1109/icidea59866.2023.10295183
  12. Maximizing Efficiency using Fuzzy Matrix Optimization for Wireless Resource Allocation. Applied Mathematics & Information Sciences. 2024;18(6):1495-1506. doi:10.18576/amis/180625
  13. Leveraging Fuzzy Logic for Habitat Suitability Analysis: A Comprehensive Case Study in Digital Ecosystems. Applied Mathematics & Information Sciences. 2025;19(2):335-347. doi:10.18576/amis/190210
  14. Suleiman Mohammad, Yogeesh N, Khaleel Ibrahim Al-Daoud, N Raja, Manoj C R, Raghavendra M H, Asokan Vasudevan, et al. A Mathematical Fuzzy Model for Syntax-Pragmatics Interface. Forum for Linguistic Studies. 2025;7(6). doi:10.30564/fls.v7i6.9618
  15. Yogeesh N, et al. Quantum implementation of fuzzy logic conjunction and disjunction using multiqubit gates. European Chemical Bulletin. 2023;12(5):2098–2108. doi:10.48047/ecb/2023.12.5.145.
  16. Optimizing MIMO Antenna Performance Using Fuzzy Logic Algorithms. Applied Mathematics & Information Sciences. 2025;19(2):349-364. doi:10.18576/amis/190211
  17. Yogeesh N, Sayed A. Theoretical framework of quantum perspectives on fuzzy mathematics: unveiling neural mechanisms of consciousness and cognition. NeuroQuantology. 2017;15(4):180–187. doi:10.48047/nq.2017.15.4.1148.
  18. Peng Y, Zhu X, Nie F, Kong W, Ge Y. Fuzzy graph clustering. Information Sciences. 2021;571:38-49. doi:10.1016/j.ins.2021.04.058
  19. Cangemi D, D’Urso P, De Giovanni L, Federico L, Vitale V. Fuzzy Clustering and Community Detection: An Integrated Approach. Journal of Classification. 2025. doi:10.1007/s00357-025-09520-7
  20. Zhang Y, Yan S, Zhang L, Du B. Fast Projected Fuzzy Clustering With Anchor Guidance for Multimodal Remote Sensing Imagery. IEEE Transactions on Image Processing. 2024;33:4640-4653. doi:10.1109/tip.2024.3444323
  21. Dunn JC. A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters. Journal of Cybernetics. 1973;3(3):32-57. doi:10.1080/01969727308546046
  22. Bezdek JC, Ehrlich R, Full W. FCM: The fuzzy c-means clustering algorithm. Computers & Geosciences. 1984;10(2-3):191-203. doi:10.1016/0098-3004(84)90020-7
  23. Krishnapuram R, Keller JM. The possibilistic C-means algorithm: insights and recommendations. IEEE Transactions on Fuzzy Systems. 1996;4(3):385-393. doi:10.1109/91.531779
  24. Kaushal M, Danish Lohani QM, Castillo O. Weighted Intuitionistic Fuzzy C-Means Clustering Algorithms. International Journal of Fuzzy Systems. 2024;26(3):943-977. doi:10.1007/s40815-023-01644-5
Support