Computationally efficient sup-t transitive closure for sparse fuzzy binary relations. (English) Zbl 1085.03044
For the use of fuzzy relations in knowledge representation it is important to determine their sup-t-transitive closures. The authors consider fuzzy relations over finite universes of discourse, which thus are representable by square matrices, and assume that the representing matrices for their fuzzy relations are sparse matrices.
For this particular case the paper offers two algorithms to determine transitive closures, and it discusses, theoretically and with computational tests, their complexity and, shows that they have lower computational complexity than the standard approach for the general case.
For this particular case the paper offers two algorithms to determine transitive closures, and it discusses, theoretically and with computational tests, their complexity and, shows that they have lower computational complexity than the standard approach for the general case.
Reviewer: Siegfried J. Gottwald (Leipzig)
MSC:
| 03E72 | Theory of fuzzy sets, etc. |
| 68T30 | Knowledge representation |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Keywords:
fuzzy relations; sparse matrices; transitive closure; sup-t-transitivity; computational complexity; fuzzy partial orderingSoftware:
WordNetReferences:
| [1] | Engl. transl. Sov. Math. 3 (1962) 1259-1263.; Engl. transl. Sov. Math. 3 (1962) 1259-1263. |
| [2] | G. Akrivas, G. Stamou, Fuzzy semantic association of audiovisual document descriptions, Internat. Workshop on Very Low Bitrate Video Coding (VLBV), Athens, Greece, October 2001.; G. Akrivas, G. Stamou, Fuzzy semantic association of audiovisual document descriptions, Internat. Workshop on Very Low Bitrate Video Coding (VLBV), Athens, Greece, October 2001. |
| [3] | Akrivas, G.; Wallace, M.; Andreou, G.; Stamou, G.; Kollias, S., Context—Sensitive Semantic Query Expansion (2002), ICAIS, Divnomorskoe: ICAIS, Divnomorskoe Russia |
| [4] | T. Athanasiadis, Y. Avrithis, Adding semantics to audiovisual content: the FAETHON project, in: P. Enser, Y. Kompatsiaris, N.E. O’Connor, et al. (Eds.), Image and Video Retrieval, Lecture Notes in Mathematics, vol. 3115, Springer, Berlin, 2004, pp. 665-673.; T. Athanasiadis, Y. Avrithis, Adding semantics to audiovisual content: the FAETHON project, in: P. Enser, Y. Kompatsiaris, N.E. O’Connor, et al. (Eds.), Image and Video Retrieval, Lecture Notes in Mathematics, vol. 3115, Springer, Berlin, 2004, pp. 665-673. |
| [5] | Avrithis, Y.; Stamou, G.; Wallace, M.; Marques, F.; Salembier, P.; Giro, X.; Haas, W.; Vallant, H.; Zufferey, M., Unified access to heterogeneous audiovisual archives, J. Universal Comput. Sci., 9, 6, 510-519 (2003) |
| [6] | R.C. Backhouse, Calculating the Floyd-Warshall path algorithm, Eindhoven University of Technology, 1992.; R.C. Backhouse, Calculating the Floyd-Warshall path algorithm, Eindhoven University of Technology, 1992. |
| [7] | Backhouse, R. C.; van den Eijnde, J. P.H. W.; van Gasteren, A. J.M., Calculating path algorithms, Sci. Comput. Programming, 22, 3, 3-19 (1994) · Zbl 0818.68117 |
| [8] | R.C. Backhouse, A.J.M. van Gasteren, Calculating a Path Algorithm, 2nd Internat. Conf. on Mathematics of Program Construction, 1992, Lecture Notes in Computer Science, vol. 669, Springer, Berlin, 1993, pp. 32-44.; R.C. Backhouse, A.J.M. van Gasteren, Calculating a Path Algorithm, 2nd Internat. Conf. on Mathematics of Program Construction, 1992, Lecture Notes in Computer Science, vol. 669, Springer, Berlin, 1993, pp. 32-44. · Zbl 0791.68128 |
| [9] | Baker, J. J., A note on multiplying Boolean matrices, Comm. ACM, 5, 2, 102 (1962) |
| [10] | Bedek, J. C.; Biswas, G.; Huang, L. Y., Transitive closures of fuzzy thesauri for information retrieval systems, Internat. J. Man-Mach. Stud., 25, 343-356 (1986) |
| [11] | Boixader, D.; Jacas, J.; Recasens, J., Transitive closure and betweenness relations, Fuzzy Sets and Systems, 120, 415-422 (2001) · Zbl 0981.03054 |
| [12] | Chen, S.-M.; Horng, Y.-J.; Lee, C.-H., Fuzzy information retrieval based on multi-relationship fuzzy concept networks, Fuzzy Sets and Systems, 140, 183-205 (2003) · Zbl 1053.68042 |
| [13] | Dasgupta, M.; Deb, R., Factoring fuzzy transitivity, Fuzzy Sets and Systems, 118, 489-502 (2001) · Zbl 1017.91012 |
| [14] | P. Dawyndt, H. De Meyer, B. De Baets, The complete linkage clustering algorithm revisited, Soft Comput. 9 (5) (2005) 385-392.; P. Dawyndt, H. De Meyer, B. De Baets, The complete linkage clustering algorithm revisited, Soft Comput. 9 (5) (2005) 385-392. |
| [15] | De Baets, B.; De Meyer, H., On the existence and construction of T-transitive closures, Inform. Sci., 152, 167-179 (2003) · Zbl 1040.03039 |
| [16] | De Baets, B.; De Meyer, H., Transitive approximation of fuzzy relations by alternating closures and openings, Soft Comput., 210-219 (2003) · Zbl 1024.03056 |
| [17] | B. De Baets, H. De Meyer, H. Naessens, A top-down algorithm for generating the Hasse tree of a fuzzy preorder closure, IEEE Trans. Fuzzy Systems 12 (6) (2004) 838-848.; B. De Baets, H. De Meyer, H. Naessens, A top-down algorithm for generating the Hasse tree of a fuzzy preorder closure, IEEE Trans. Fuzzy Systems 12 (6) (2004) 838-848. |
| [18] | Duan, J.-S., The transitive closure, convergence of powers and adjoint of generalized fuzzy matrices, Fuzzy Sets and Systems, 145, 301-311 (2004) · Zbl 1068.15022 |
| [19] | Dunn, J. C., A graph-theoretical analysis of pattern classification via Tamura’s fuzzy relation, IEEE Trans. SMC, 5, 310-313 (1974) · Zbl 0297.68077 |
| [20] | Dunn, J. C., Some recent investigations of a new fuzzy partitioning algorithm and its applications to pattern classification problems, J. Cybernet., 4, 1-15 (1974) · Zbl 0304.68094 |
| [21] | Feijs, L. M.G.; van Ommering, R. C., Abstract derivation of transitive closure algorithms, Inform. Process. Lett., 63, 159-164 (1997) · Zbl 1337.68283 |
| [22] | C. Fellbaum (Ed.), WordNet: An Electronic Lexical Database, MIT Press, Cambridge, MA, 1998.; C. Fellbaum (Ed.), WordNet: An Electronic Lexical Database, MIT Press, Cambridge, MA, 1998. · Zbl 0913.68054 |
| [23] | Fodor, J.; Roubens, M., Structure of transitive valued binary relations, Math. Soc. Sci., 30, 71-94 (1995) · Zbl 0886.90004 |
| [24] | Guu, S.-M.; Chen, H.-H.; Pang, C.-T., Convergence of products of fuzzy matrices, Fuzzy Sets and Systems, 121, 203-207 (2001) · Zbl 0994.15017 |
| [25] | Klir, G.; Yuan, B., Fuzzy Sets and Fuzzy Logic: Theory and Applications (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0915.03001 |
| [26] | Kundu, S., A representation theorem for min-transitive fuzzy relations, Fuzzy Sets and Systems, 109, 453-457 (2000) · Zbl 0946.03065 |
| [27] | Lee, H.-S., An optimal algorithm for computing the max-min transitive closure of a fuzzy similarity matrix, Fuzzy Sets and Systems, 123, 129-136 (2001) · Zbl 1003.65043 |
| [28] | A. Maedche, B. Motik, N. Silva, R. Volz, MAFRA—An Ontology MApping FRAmework in the Context of the SemanticWeb, Workshop on Ontology Transformation, ECAI, 2002.; A. Maedche, B. Motik, N. Silva, R. Volz, MAFRA—An Ontology MApping FRAmework in the Context of the SemanticWeb, Workshop on Ontology Transformation, ECAI, 2002. |
| [29] | De Meyer, H.; Naessens, H.; De Baets, B., Algorithms for computing the min-transitive closure and associated partition tree of a symmetric fuzzy relation, European J. Oper. Res., 155, 226-238 (2004) · Zbl 1043.90087 |
| [30] | Naessens, H.; De Meyer, H.; De Baets, B., Algorithms for the computation of T-transitive closures, IEEE Trans. Fuzzy Systems, 10, 541-551 (2002) |
| [31] | Ovchinnikov, S., Numerical representation of transitive fuzzy relations, Fuzzy Sets and Systems, 126, 225-232 (2002) · Zbl 0996.03510 |
| [32] | Purdom, P., A transitive closure algorithm, BIT, 10, 76-94 (1970) · Zbl 0193.14604 |
| [33] | Seidel, R., On the all-pairs-shortest-path problem in unweighted undirected graphs, J. Comput. System Sci., 51, 400-403 (1995) · Zbl 1295.05240 |
| [34] | G. Stamou, Y. Avrithis, S. Kollias, F. Marques, P. Salembier, Semantic unification of heterogenous multimedia archives, Proc. of 4th European Workshop on Image Analysis for Multimedia Interactive Services (WIAMIS), London, UK, April 9-11, 2003.; G. Stamou, Y. Avrithis, S. Kollias, F. Marques, P. Salembier, Semantic unification of heterogenous multimedia archives, Proc. of 4th European Workshop on Image Analysis for Multimedia Interactive Services (WIAMIS), London, UK, April 9-11, 2003. |
| [35] | Tan, Y.-J., On compositions of lattice matrices, Fuzzy Sets and Systems, 129, 19-28 (2002) · Zbl 1014.15011 |
| [36] | Thorelli, L.-E., An algorithm for computing all paths in a graph, BIT, 6, 347-349 (1966) · Zbl 0144.45503 |
| [37] | Ullman, J. D.; Yannakakis, M., The input/output complexity of transitive closure, Ann. Math. Artif. Intell., 331-360 (1991) · Zbl 0875.68239 |
| [38] | Wallace, M.; Akrivas, G.; Mylonas, P.; Avrithis, Y.; Kollias, S., Using context and fuzzy relations to interpret multimedia content (2003), CBMI: CBMI IRISA, Rennes, France |
| [39] | Wallace, M.; Akrivas, G.; Stamou, G., Automatic Thematic Categorization of Documents Using a Fuzzy Taxonomy and Fuzzy Hierarchical Clustering (2003), FUZZ-IEEE: FUZZ-IEEE St. Louis, MO, USA |
| [40] | Wallace, M.; Akrivas, G.; Stamou, G.; Kollias, S., Representation of user preferences and adaptation to context in multimedia content-based retrieval (2002), Workshop on Multimedia Semantics: Workshop on Multimedia Semantics SOFSEM, Milovy, Czech Republic |
| [41] | Wallace, M.; Avrithis, Y.; Stamou, G.; Kollias, S., (Stamou, G.; Kollias, S., Knowledge-based Multimedia Content Indexing and Retrieval (2004), Multimedia Content and Semantic Web: Methods, Standards and Tools: Multimedia Content and Semantic Web: Methods, Standards and Tools Wiley, New York) |
| [42] | Warren, H. S., A modification of Warshall’s algorithm for the transitive closure of binary relations, Comm. ACM, 18, 4, 218-220 (1975) · Zbl 0309.94048 |
| [43] | Warshall, S., A theorem on Boolean matrices, J. ACM, 9, 1, 11-12 (1962) · Zbl 0118.33104 |
| [44] | Yoshida, Y., A limit theorem in dynamic fuzzy systems with transitive fuzzy relations, Fuzzy Sets and Systems, 109, 371-378 (2000) · Zbl 0944.54007 |
| [45] | Zadeh, L. A., Fuzzy Sets, Inform. Control, 3, 338-353 (1965) · Zbl 0139.24606 |
| [46] | Zadeh, L. A., Similarity relations and fuzzy orderings, Inform. Sci., 3, 177-200 (1971) · Zbl 0218.02058 |
| [47] | \( \sim;\); \( \sim;\) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
