Semirings in Operations Research and Computer Science: More Algebra

Rudeanu, S.; Vaida, D.

Artykuł - szczegóły

Tytuł artykułu

Semirings in Operations Research and Computer Science: More Algebra

Autorzy

Rudeanu S. , Vaida D.

Wybrane pełne teksty z tego czasopisma

https://fi.episciences.org/

Identyfikatory

Warianty tytułu

Języki publikacji

Abstrakty

We undertake an axiomatic study of certain semirings and related structures that occur in operations research and computer science. We focus on the properties A,I,U,G,Z,L that have been used in the algebraic study of path problems in graphs and prove that the only implications linking the above properties are essentially those already known. On the other hand we extend those implications to the framework of left and right variants of A,I,U,G,Z,L, and we also prove two embedding theorems. Further generalizations refer mainly to semiring-like algebras with a partially defined addition, which is needed in semantics. As suggested by idempotency (I) and absorption (A), we also examine in some detail the connections between semirings and distributive lattices, which yield new systems of axioms for the latter.

Słowa kluczowe

semiring optimal path problem fuzzy modelling partial additive semantics process algebras complete existential theory

Wydawca

IOS Press

Czasopismo

Fundamenta Informaticae

Rocznik

2004

Tom

Vol. 61, nr 1

Strony

61--85

Opis fizyczny

Bibliogr. 59 poz.

Twórcy

autor

Rudeanu S.

rud@funinf.math.unibuc.ro

Faculty of Mathematics and Computer Science, Bucharest University, Str. Academiei 14, 010014 Bucharest, Romania

autor

Vaida D.

Faculty of Mathematics and Computer Science, Bucharest University, Str. Academiei 14, 010014 Bucharest, Romania

Bibliografia

1. J.C.M. Baeten, W.P.Weijland: [1990] Process Algebra, Cambridge Tracts in Theoretical Computer Science, Cambridge Univ. Press, Cambridge.
2. M. Benado: [1955] Les ensembles partiellement ordonnes et le théorème de raffinement de Schreier, Czechoslovak Math. J. 5(80,3), 308-344.
3. C. Benzaken: [1968] Contribution des structures algèbriques ordonnèes à la thèorie des réseaux, These, Univ. Grenoble.
4. J.H. Bevis: [1974] Free gerbiers and nets. Math. Systems Theory 8,127-131.
5. G. Birkhoff: [1967] Lattice Theory, Third ed. Third printing, 1979. Amer. Math. Soc, Providence, RI.
6. D. Butnariu, E.P. Klement: [1993] Triangular Norm-Based Measures and Games with Fuzzy Coalitions, Series C: Game Theory, Math. Programming and Operations Res. vol. 10, Kluwer Acad. Publ., Dordrecht.
7. Z.-Cao, K.H. Kim, F.W. Roush: [1984] Incline Algebra and Applications, Ellis Horwood Ltd, Chichester, & J. Wiley, New York.
8. B.A. Carre: [1971] An algebra for network routing problems, J. Inst. Math. Appl., 7, 273-294.
9. R. Cruon, Ph. Herve: [1965] Quelques résultats relatifs à une structure algébrique et à son application au problème central de I'ordonnancement, Rev. Française Rech. Oper. 34, 3-19.
10. R. Cuninghame-Green: [1919] Minimax Algebra, Lecture Notes Econ. Math. Systems no. 166, Springer-Verlag, Berlin.
11. R. Dedekind: [1894] Über die Theorie der ganzen algebraischen Zahlen, Supplement XI to P.G. Lejeune Dirichlet, Vorlesungen liber Zahlentheorie, 4te Aufl., Druck und Verlag, Braunschweig.
12. J.S. Golan: [1992] The Theory of Semirings with Aplications in Mathematics and Theoretical Computer Science, Pitman Monographs and Surveys Pure Appl. Math. vol. 54. Longman Sci. & Techn.
13. M. Gondran: [1975] Algebre linéaire et cheminement dans un graphe. Rev. Française Autom. Informat. Rech. Open Ser. Verte 9, 77-99.
14. H. Hashimoto: [1983] Transitivity of matrices over a path algebra, Preprint, Yamaguchi Univ., Yamaguchi.
15. U. Hebisch, H.J. Weinert: [1999] Semirings -Algebraic Theory and Applications in Computer Science, Ser. Alg., vol. 5. World Sci., Singapore.
16. G.J. Klir, B. Yuan: [1995] Fuzzy Sets and Fuzzy Logic, Prentice Hall, New Jersey.
17. E.G. Manes, M.A. Arbib: [1986] Algebraic Approach to Program Semantics, Springer-Verlag, Berlin.
18. M. Minoux: [1976] Structures algébriques généralisées des problèmes de che-minement dans les graphes: théorèmes, algorithmes et applications. Rev. Fran- 9aise Informat. Rech. Open (RAIRO) Rech. Open 10, 33-62.
19. Gr.C. Moisil: [1960] Asupra unor reprezentari ale grafurilor ce intervin in probleme de economia transporturilor. Com. Acad. R.P.Romane 10, 647-652.
20. E.H. Moore: [1910] Introduction to a Form of General Analysis, New Haven Colloq., 1906. New Haven.
21. L. Nolin: [1964] Traitement des données groupées, Inst. Blaise Pascal, Paris.
22. V. Peteanu: [1967]: An algebra of optimal paths in networks, Mathematica (Cluj) 9(32), 335-342.
23.: [1969] Optimal paths in networks and generalizations, I. Mathematica (Cluj) 11(34), 311-327. 11. ibid. 12(35) (1970), 159-187.
24. G.N. Povarov: [1960] Qualitative analysis of electrical circuits with finite conductibilities by means of the theory of cumulative nets (Russian), Doklady Akad. Nauk SSSR 136, no.2.
25.: — [1962] The theory of numeroids in the algebra of automata (Russian), Problemy peredachi informacii no.l 1, Izd-vo Akad. Nauk SSSR , Moskva.
26. P. Robert, J. Ferland: [1968]. Généralisation de I'algorithme de Warshall, Rev. Frangaise Informat. Rech. Open (RIRO) 2, 71-85.
27. B. Roy: [1959] Transitivite et connexite, C.R. Acad. Sci. Paris 249, 216-218.
28. S. Rudeanu: [1963] Axiomele laticilor şi ale algebrelor booleene, Ed. Acade-miei R.P.Romane, Bucharest.
29. M. Sholander : [1951] Postulates for distributive lattices, Canad. J. Math. 3, 28-30.
30. F.A. Smith: [1966] A structure theory for a class of lattice-ordered semi-rings, Fund. Math. 59, 49-64.
31. M.E. Steenstrup: [1985] Sum-ordered partial semirings, PhD Thesis, Univ. Massachusetts, Boston, February 1985.
32. I. Tomescu: [1966] Sur les méthodes matricielles dans la théorie des réseaux, C.R. Acad. Sci. Paris 263, 826-829.
33. — [1967] Asupra unor metode matriciale care intervin in teoria reţelelor. Stud. Cere. Mat. 19,105-118.
34. — [1968] Sur I'algorithme matriciel de B. Roy, Rev. Fran9aise Informat. Rech. Opér (RIRO) 2, 87-91.
35. — [1972] Structuri algebrice ordonate in teoria grafurilor. Stud. Cere. Mat. 24, 469-476.
36. — [2001] A cascade version of Dantzig's inductive algorithm for matrices over semilattice ordered semigroups. Multiple Val. Logic 6, 217-228.
37. D. Vaida: [2001] On partially additive semirings and applications, Mult.-Val. Logic 6, 251-266.
38. H.S.Vandiver: [1939] On some simple types of semi-rings, Amer. Math. Monthly 46, 22-26.
39. H.S. Vandiver, M.H. Weaver: [1956] A development of associative algebra and an algebraic theory of numbers, IV. Math. Mag. 30, 1-8.
40. S. Warshall: [1962] A theorem on Boolean matrices, J. Assoc. Comput. Mach. 9, 11-12.
41. M. Yoeli: [1961] Note on a generalization of Boolean matrix theory, Amer. Math. Monthly 68, 552-557.
42. L.A. Zadeh: [1965] Fuzzy sets. Information and Control 8, 338-353.
43. H.J. Zassenahus: [1958] The Theory of Groups (2nd ed), Chelsea, New York.
44. U. Zimmerman: [1981] Linear and Combinatorial Optimization in Ordered Algebraic Structures, North-Holland, Amsterdam.
A bibliography of complete existential theories
1 . A.H. Diamond, The complete existential theory of the Whitehead-Russell set of postulates for the algebra of logic, Trans. Amer. Math. Soc. 35 (1933), 940-948; correct, ibid. (1934), 893.
2 . L.L. Dines, Complete existential theory of Sheffer's postulates for Boolean algebras. Bull. Amer. Math. Soc. 21 (1914/15), 183-188.
3 . M.-L. Dubreil-Jacotin, L. Lesieur, R. Croisot, Leşons sur la théorie des treillis, des structures algébriques ordonnées et des treillis géométriques, Gauthier-Villars, Paris 1953.
4 . E.V. Huntington, Complete existential theory for serial order. Bull. Amer. Math. Soc. 23 (1917), 276-280.
5 . E.W. Huntington, Sets of completely independent postulates for cyclic order, PTOC. Nat. Acad. Sci. USA 10 (1924), 74-78.
6 . E.V. Huntington, A new set of postulates for betweenness, with a proof of complete independence, Trans. Amer. Math. Soc. 26 (1924), 257-282.
7 . H.M. MacNeille, Partially ordered sets, Trans. Amer. Math. Soc. 42 (1937), 416-460.
8 . E.H. Moore, Introduction to a form of general analysis. New Haven Colloq. 1906 (New Haven, 1910).
9 . G. Petre, Teoria complet existenţiala a proprietaţilor relaţiilor binare, Gaz. Mat. 20(99) (2002), 226-238.
10 . I. Rosenbaum, A new system of completely independent postulates for betweenness. Bull. Amer. Math. Soc. 57 (1951), 279.
11 . S. Rudeanu, Logical dependence of certain chain conditions in lattice theory, Acta Sci. Math. (Szeged) 25( 1964), 209-218.
12 . S. Rudeanu, Elemente de teoria mulţimilor, Univ. Bucureşti, 1973.
13 . J.S. Taylor, Complete existential theory of Bernstein's set of postulates for Boolean algebras, Ann. Math. 19 (1917), 64-69.
14 . J.S. Taylor, Sheffer's set of five independent postulates for Boolean algebras in terms of the operation "rejection" made completely independent. Bull. Amer. Math. Soc. 26 (1920), 449-454.
15 . W.E. Van de Walk, On the complete independence of the postulates for betweenness, Trans. Amer. Math. Soc. 26 (1924), 249-256.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BUS2-0005-0054