Algorithms to Compute The Demonic Transitive Closure of Fuzzy Relations Using Demonic Operators

Abstract

In this paper, we investigate the demonic transitive closure of fuzzy relations in the sense of demonic operators. To address this, we focus on the demonic order refinement of fuzzy relations, which has a special treatment associated with the membership function of fuzzy relations. We look closely at the transitive closure of fuzzy relations with the use of angelic operators (the usual operators ∪, ∩ and ◦) and reform it by applying the demonic operators (˜⊔, ˜⊓ and ˜□ ). In order to carry out this task, we adopt existing algorithms and reformulate them in the means of demonic operators.

Keywords

• Transitive Closure
• Demonic Transitive Closure
• Demonic Fuzzy Operators

References

1. Alrashidi, H.: Demonic operators on fuzzy relations illustration with mathematica. Master’s thesis, King Saud University (2011).
2. Backhouse, R. C. and van der Woude, J.: Demonic Operators and Monotype Factors. Mathematical Structures in Comput. Sci., 3(4), 417–433 (1993). Also: Computing Science Note 92/11, Department of Mathematics and Computer Science, Eindhoven University of Technology, The Netherlands, (1992).
3. Bandler, W., Kohout, L. J.: Special properties, closures and interiors of crisp and fuzzy relations. Fuzzy sets and Systems, 26(3), 317–331 (1988).
4. Buckley, J. J., Eslami, E., Feuring, T.: Fuzzy mathematics in economics and engineering. Physica, Vol. 91, Springer, Heidelberg (2013).
5. De Baets, B., De Meyer, H.: On the existence and construction of T-transitive closures. newblock Information Sciences, 152, 167–179 (2003).
6. De Baets, B. and De Meyer, H.: T-transitive closures, openings and approximations of similarity relations. 2002 IEEE World Congress on Computational Intelligence. 2002 IEEE International Conference on Fuzzy Systems. FUZZ-IEEE’02. Proceedings (Cat. No.02CH37291), 1375–1380 (2002).
7. Desharnais, J. Mili, A. and Nguyen, T.T.: Refinement and demonic semantics, in:C. Brink, W.khal,G.Schmidt(Eds), Relational methods in Computer Science. Advances in Computing . pp. 166–183. Springer-Wein, New York (1997).
8. Desharnais, J., Belkhiter, N., Ben Mohamed Sghaier, S., Tchier, F., Jaoua, A., Mili, A. and Zaguia, N.: Embedding a Demonic Semilattice in a Relation Algebra. Theoretical Computer Science, 149(2), 333–360 (1995).

9. Floyd, R. W.: Algorithm 97: Shortest path. Commun. ACM, 5(6), 345 (1962).
10. Garmendia Salvador, L., González del Campo, R., López, V., Recasens Ferrés, J.: An algorithm to compute the transitive closure, a transitive approximation and a transitive opening of a fuzzy proximity. Mathware and soft computing, 16(2), 175–191 (2009).
11. Jagadish, H. V.: A compression technique to materialize transitive closure.
12. Larsen, H., Yager, R.: Efficient computation of transitive closures. Fuzzy Sets and Systems, 38, 81–90 (1990).
13. Lee, H. S.: An optimal algorithm for computing the max–min transitive closure of a fuzzy similarity matrix. Fuzzy sets and systems, 123(1), 129–136 (2001).
14. Naessens, H., De Meyer, H., and De Baets, B.: Algorithms for the computation of T-transitive closures. IEEE Transactions on Fuzzy Systems, 10, 541–551 (2002).
15. Tchier, F.: Demonic Semantics: using monotypes and residuals. Journal of Math- ematics and Mathematical Sciences 3(2004), 135-160 (2004).
16. Tchier, F.: Relational Demonic Fuzzy Refinement. Journal of Applied Mathematics, (2014).
17. Vila, M. A. and Delgado, M.: On medical diagnosis using possibility measures. FSS 10, 211–222 (1983).
18. Warshall, S.: A theorem on boolean matrices. Journal of the ACM, 9(1), 11–12 (1962).
19. Zadeh, L. A. .: Similarity relations and fuzzy orderings. Information Science 3, 177–206 (1971).
20. Zadeh, L. A. .: Fuzzy Sets. Inform and Control 8, 338–353 (1965).