×

zbMATH — the first resource for mathematics

Dioïds and semirings: Links to fuzzy sets and other applications. (English) Zbl 1117.06010
Summary: Besides the classical algebraic structures of groups, rings and fields, which have long been the almost exclusive reference concepts used in mathematical modelling, other algebraic structures such as dioïds and semirings have emerged in the last two or three decades in connection with modelling and solving a rich variety of non-classical problems, e.g. in decision analysis, fuzzy set theory, operations research, automatic control and mathematical physics. The present paper aims at providing an overview of applications of dioïd and semiring structures, stressing links with fuzzy sets and emphasizing linear algebraic problems (solving linear systems, computing eigenvalues and eigenvectors), nonclassical path-finding problems (using algebras of endomorphisms) and connections between dioïd structure and nonlinear analysis (in view of solving problems in mathematical physics).
Reviewer: Reviewer (Berlin)

MSC:
06F25 Ordered rings, algebras, modules
08A72 Fuzzy algebraic structures
16Y60 Semirings
03E72 Theory of fuzzy sets, etc.
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] K.S. Abdali, D.B. Saunders, Transitive closure and related semiring properties via eliminants, in: R.C. Backhouse, B.A. Carré (Eds.), 1975. · Zbl 0618.16036
[2] F. Baccelli, G. Cohen, G.J. Olsder, J.P. Quadrat, Synchronization and Linearity. An Algebra for Discrete Event Systems, Wiley, New York, 1992, 489pp. · Zbl 0824.93003
[3] Backhouse, R.C.; Carré, B.A., Regular algebra applied to path-finding problems, J. inst. math. appl., 15, 161-186, (1975) · Zbl 0304.68082
[4] Berge, C., La théorie des graphes et ses applications, (1958), Dunod (Libraire) Paris · Zbl 0214.50804
[5] Berge, C., Balanced matrices, Math. program., 2, 1, 19-31, (1972) · Zbl 0247.05126
[6] Butkovic, P.; Cechlarova, K.; Szabo, P., Strong linear independence in bottleneck algebra, Linear algebra appl., 94, 133-155, (1987) · Zbl 0629.90093
[7] Cao, Z.Q.; Kim, K.H.; Roush, F.W., Incline algebra and applications, (1984), Ellis Horwood, Wiley Chichester, UK, New York · Zbl 0541.06009
[8] Carre, B.A., An algebra for network routing problems, J. inst. math. appl., 7, 273-294, (1971) · Zbl 0219.90020
[9] Cechlárová, K., Eigenvectors in bottleneck algebra, Linear algebra appl., 175, 63-73, (1992) · Zbl 0756.15014
[10] Cechlárová, K., Unique solvability of max – min fuzzy equations and strong regularity of matrices over fuzzy algebra, Fuzzy sets and systems, 75, 2, 165-177, (1995) · Zbl 0852.15011
[11] Cechlárová, K., On the powers of matrices in bottleneck/fuzzy algebra, Linear algebra appl., 246, 97-112, (1996) · Zbl 0866.15009
[12] Cechlárová, K., Powers of matrices over distributive lattices—a review, Fuzzy sets and systems, 138, 3, 627-641, (2003) · Zbl 1075.05537
[13] Cechlárová, K.; Plávka, J., Linear independence in bottleneck algebras, Fuzzy sets and systems, 77, 3, 337-348, (1996) · Zbl 0877.15017
[14] Chang, C.C., Algebraic analysis of many valued logics, Trans. amer. math. soc., 93, 74-80, (1958) · Zbl 0084.00704
[15] Choquet, G., Theory of capacities, Annales de l’institut Fourier, 5, 131-295, (1953) · Zbl 0064.35101
[16] Cohen, G.; Dubois, D.; Quadrat, J.-P.; Viot, M., A linear system—theoretic view of discrete event processes and its use for performance evaluation in manufacturing, IEEE trans. automat. control AC, 30, 3, 210-220, (1985) · Zbl 0557.93005
[17] Cruon, R.; Herve, Ph., Quelques problèmes relatifs à une structure algébrique et à son application au problème central de l’ordonnancement, Revue fr. rech. op., 34, 3-19, (1965) · Zbl 0143.42002
[18] Cuninghame-Green, R.A., Process synchronisation in a steelworks—a problem of feasibility, (), 323-328
[19] Cuninghame-Green, R.A., Describing industrial processes with interference and approximating their steady-state behaviour, Oper. res. quart., 13, 1, 95-100, (1962)
[20] Cuninghame-Green, R.A., Minimax algebra: lecture notes, () · Zbl 0498.90084
[21] Cuninghame-Green, R.A., Minimax algebra and applications, Fuzzy sets and systems, 41, 3, 251-267, (1991) · Zbl 0739.90073
[22] Cuninghame-Green, R.A., Maxpolynomial equations, Fuzzy sets and systems, 75, 2, 179-187, (1995) · Zbl 0857.90134
[23] Cuninghame-Green, R.A.; Cechlárová, K., Residuation in fuzzy algebra and some applications, Fuzzy sets and systems, 71, 2, 227-239, (1995) · Zbl 0845.04007
[24] G.B. Dantzig, W.D. Blattner, M.R. Rao, Finding a cycle in a graph with minimum cost to time ratio with application to a ship routing problem, in: Proc. Internat. Symp. on Théorie des graphes, Rome, Italy, Dunod, Paris, 1967, pp. 77-83. · Zbl 0189.24102
[25] R. Dautray, J.L. Lions, Analyse mathématique et calcul numérique pour les sciences et les techniques, Tome 3, Masson, Paris (New York), 1985. · Zbl 0642.35001
[26] Defays, D., Analyse hiérarchique des préférences et généralisations de la transitivité, Math. sci. humaines, 61, 5-27, (1978) · Zbl 0408.90007
[27] A. Di Nola, B. Gerla, Algebras of Lukasiewicz’s logic and their semirings reducts, in: Proc. Conf. on Idempotent Mathematics and Mathematical Physics, to appear. · Zbl 1081.06009
[28] Di Nola, A.; Lettieri, A.; Perfilieva, I.; Novák, V., Algebraic analysis of fuzzy systems, Fuzzy sets and systems, 158, 1, 1-22, (2007) · Zbl 1110.93012
[29] Dubois, D.; Prade, H., Fuzzy sets and systems—theory and applications, (1980), Academic Press New York · Zbl 0444.94049
[30] D. Dubois, H. Prade, Théorie des possibilités. Application à la représentation des connaissances en informatique, second ed., Masson, Paris, 1987. · Zbl 0674.68059
[31] Dubois, D.; Prade, H., Fuzzy sets in approximate reasoning—part 1: inference with possibility distributions, Fuzzy sets and systems, 40, 143-202, (1991) · Zbl 0722.03017
[32] Fan, Z.T., On the convergence of a fuzzy matrix in the sense of triangular norms, Fuzzy sets and systems, 109, 409-417, (2000) · Zbl 0980.15013
[33] Gavalec, M., Computing matrix period in max – min algebra, Discrete appl. math., 75, 63-70, (1997) · Zbl 0876.05070
[34] Gavalec, M., Monotone eigenspace structure in max – min algebra, Linear algebra appl., 345, 149-167, (2002) · Zbl 0994.15010
[35] A. Ghouila-Houri, Caractérisation des matrices totalement unimodulaires, Tome 254, C.R.A.S., Paris, 1962, 1192. · Zbl 0114.25102
[36] P.H. Giang, P.P. Shenoy, A comparison of axiomatic approaches to qualitative decision making using possibility theory, in: Proc. 17th Conf. on Uncertainty in Artificial Intelligence, 2001, pp. 162-170.
[37] Giffler, B., Scheduling general production systems using schedule algebra, Naval res. logist. quart., 10, 3, (1963)
[38] Golan, J.S., Semirings and their applications, (1999), Kluwer Academic Publishers Dordrecht · Zbl 0947.16034
[39] Gondran, M., Path algebra and algorithms, () · Zbl 0326.90060
[40] Gondran, M., L’algorithme glouton dans LES algèbres de chemins, bulletin de la direction etudes et recherches, EDF, Série C, 1, 25-32, (1975)
[41] Gondran, M., Eigenvalues and eigenvectors in hierarchical classification, (), 775-781 · Zbl 0362.62062
[42] Gondran, M., LES éléments p-réguliers dans LES dioïdes, Discrete math., 25, 33-39, (1979) · Zbl 0425.20056
[43] M. Gondran, Valeurs propres et vecteurs propres en analyse des préférences, Note EDF HI-3199, 1979.
[44] M. Gondran, Le théorème de Cayley-Hamilton dans les dioïdes, Note EDF, 1983.
[45] Gondran, M.; Minoux, M., Valeurs propres et vecteurs propres dans LES semi-modules modules et leur interprétation en théorie des graphes, bulletin de la direction etudes et recherches, EDF, Série C, 2, 25-41, (1977)
[46] Gondran, M.; Minoux, M., L’indépendance linéaire dans LES dioïdes, bulletin de la direction etudes et recherches, EDF, Série C, 1, 67-90, (1978)
[47] Gondran, M.; Minoux, M., Graphes et algorithmes, (1979), Eyrolles Paris, (English translation by Wiley, 1984) · Zbl 0497.05023
[48] Gondran, M.; Minoux, M., Linear algebra in dioïds: a survey of recent results, Ann. discrete math., 19, 147-164, (1984) · Zbl 0568.08001
[49] Gondran, M.; Minoux, M., Eigenvalues and eigen-functionals of diagonally dominant endomorphisms in min – max analysis, Linear algebra appl., 282, 47-61, (1998) · Zbl 0990.15006
[50] M. Gondran, M. Minoux, Graphes, dioïdes et semi-anneaux, Tec & Doc (Lavoisier), Paris, 2001, 415pp (English translation: Graphs, Dioïds and Semirings, Springer, Berlin, to appear).
[51] Grabisch, M., On equivalence classes of fuzzy connectives, the case of fuzzy integrals, IEEE trans. fuzzy systems, 3, 1, 96-109, (1995)
[52] Grabisch, M., The symmetric sugeno integral, Fuzzy sets and systems, 139, 473-490, (2003) · Zbl 1033.28009
[53] Grabisch, M., The Möbius function on symmetric ordered structures and its application to capacities on finite sets, Discrete math., 287, 1-3, 17-34, (2004) · Zbl 1054.06008
[54] Grabisch, M.; De Baets, B.; Fodor, J., The quest for rings on bipolar scales, Internat. J. uncertain. fuzziness knowledge-based systems, 12, 4, 499-512, (2004) · Zbl 1068.91012
[55] M. Grabisch, M. Sugeno, Multiattribute classification using fuzzy integral, in: Proc. 1st IEEE Internat. Conf. on Fuzzy System, 1992, pp. 47-54.
[56] Guo, S.Z.; Wang, P.Z.; Di Nola, A.; Sesa, S., Further contributions to the study of finite fuzzy relation equations, Fuzzy sets and systems, 26, 93-104, (1988) · Zbl 0645.04003
[57] Halpern, J.; Priess, I., Shortest paths with time constraints in movement and parking, Networks, 4, 241-253, (1974) · Zbl 0284.90077
[58] Han, S.C.; Li, H.X., Invertible incline matrices and Cramer’s rule over inclines, Linear algebra appl., 389, 121-138, (2004) · Zbl 1089.15004
[59] Hebisch, U.; Weinert, H.J., Semirings. algebraic theory and application in computer science, (1998), World Scientific Singapore, 361pp · Zbl 0934.16046
[60] Höhle, U.H.; Klement, E.P., Commutative residuated 1-monoïds, (), 53-106 · Zbl 0838.06012
[61] Johnson, S.C., Hierarchical clustering schemes, Psychometrica, 32, 241-243, (1967) · Zbl 1367.62191
[62] Jun-Sheng Duan, J.-S., The transitive closure, convergence of powers and adjoint of generalized fuzzy matrices, Fuzzy sets and systems, 145, 2, 301-311, (2004) · Zbl 1068.15022
[63] Klement, E.P.; Mesiar, R.; Pap, E., Triangular norms, (2000), Kluwer Academic Publishers Dordrecht · Zbl 0972.03002
[64] Kim, K.H.; Roush, F.W., Generalized fuzzy matrices, Fuzzy sets and systems, 4, 293-315, (1980) · Zbl 0451.20055
[65] Kim, K.H.; Roush, F.W., Inclines of algebraic structures, Fuzzy sets and systems, 72, 2, 189-196, (1995) · Zbl 0846.06010
[66] Kuntzmann, J., Théorie des réseaux graphes, (1972), Dunod (Libraire) Paris · Zbl 0239.05101
[67] Li, J.-X., The smallest solution of max – min fuzzy equations, Fuzzy sets and systems, 41, 317-327, (1990) · Zbl 0731.04006
[68] Lions, P.L., Generalized solutions of hamilton – jacobi equations, (1982), Pitman London (Melbourne) · Zbl 1194.35459
[69] Maslov, V.P., On a new principle of superposition for optimization problems, Russian math. surveys, 42, 3, 43-54, (1987) · Zbl 0707.35138
[70] V.P. Maslov, S.N. Samborskii, Idempotent Analysis, Vol. 13, Advances in Soviet Mathematics, American Mathematical Society, Providence, RI, 1992.
[71] Menger, K., Statistical metrics, Proc. nat. acad. sci. U.S.A., 28, 535-537, (1942) · Zbl 0063.03886
[72] Minoux, M., Structures algébriques généralisées des problèmes de cheminement dans LES graphes: théorèmes, algorithmes et applications, Revue fr. automatique informatique rech. op., 10, 6, 33-62, (1976) · Zbl 0337.05122
[73] M. Minoux, Generalized path algebras, in: A. Prekopa (Ed.), Surveys of Mathematical Programming, Publishing House of the Hungarian Academy of Sciences, 1977, pp. 359-364
[74] Minoux, M., Bideterminants, arborescences and extension of the matrix-tree theorem to semirings, Discrete math., 171, 191-200, (1997) · Zbl 0880.05065
[75] Minoux, M., A generalization of the all minors matrix-tree theorem to semirings, Discrete math., 199, 139-150, (1998) · Zbl 0928.15010
[76] Minoux, M., Extensions of mac Mahon’s master theorem to pre-semi-rings, Linear algebra appl., 338, 19-26, (2001) · Zbl 0992.15015
[77] P. Perny, O. Spanjaard, P. Weng, Algebraic Markov decision processes, in: Proc. Internat. Joint Conf. on Artificial Intelligence, 2005.
[78] Peteanu, V., An algebra of the optimal path in networks, Mathematica, 9, 335-342, (1967) · Zbl 0171.15305
[79] Robert, P.; Ferland, J., Généralisation de l’algorithme de warshall, Revue fr. informatique rech. op., 2, 71-85, (1968) · Zbl 0172.20601
[80] A. Shimbel, Structure in communication nets, in: Proc. Symp. on Information Networks, Polytechnic Institute of Brooklyn, 1954, pp. 119-203.
[81] O. Spanjaard, Exploitation de préférences non classiques dans les Problèmes Combinatoires. Modèles et Algorithmes pour les Graphes, Doctoral Dissertation, Université Paris Dauphine, France, 2003.
[82] Straubing, H., A combinatorial proof of the cayley – hamilton theorem, Discrete math., 43, 273-279, (1983) · Zbl 0533.15010
[83] M. Sugeno, Theory of fuzzy integrals and applications, Ph.D. Dissertation, Tokyo Institute of Technology, 1974.
[84] M. Sugeno, Fuzzy measures and fuzzy integrals: a survey, in: Gupta, Saridis, Gaines (Eds.), Fuzzy Automata and Decision Processes, 1977, pp. 89-102.
[85] Wang, Z.; Klir, G.J., Fuzzy measure theory, (1972), Plenum Press New York (London)
[86] Warshall, H., A theorem of Boolean matrices, J. ACM, 9, (1962) · Zbl 0118.33104
[87] Yoeli, M., A note on a generalization of Boolean matrix theory, Amer. math. monthly, 68, 552-557, (1961) · Zbl 0115.02103
[88] Zimmermann, U., Linear and combinatorial optimization in ordered algebraic structures, Ann. discrete math., 10, (1981) · Zbl 0466.90045
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.