×

A coalgebraic approach to non-determinism: applications to multilattices. (English) Zbl 1222.06004

Summary: Multilattices are a suitable generalization of lattices which makes it possible to accommodate the formalization of nondeterministic computation; specifically, the algebraic characterization of multilattices provides a formal framework to develop tools in several fields of computer science. On the other hand, the usefulness of coalgebra theory has been increasing in the recent years, and its importance is undeniable. In this paper, somehow mimicking the use of universal algebra, we define a new kind of coalgebras (the ND-coalgebras) that allows us to formalize nondeterminism, and show that several concepts that are widely used in computer science are, indeed, ND-coalgebras. Within this formal context, we study a minimal set of properties which provides a coalgebraic definition of multilattices.

MSC:

06B75 Generalizations of lattices
08A70 Applications of universal algebra in computer science
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adámek, J.; Herrlich, H.; Strecker, G., Abstract and Concrete Categories (1990), Wiley-Interscience · Zbl 0695.18001
[2] Aguilera, G.; Burrieza, A.; Cordero, P.; de Guzmán, I. P.; Muñoz, E., MAT Logic: a temporal × modal logic with non-deterministic, Lecture Notes in Computer Science, 4140, 602-611 (2006)
[3] Barr, M.; Wells, C., Category Theory for Computing Science (1990), Prentice Hall International · Zbl 0714.18001
[4] Benado, M., Asupra unei generalizaˇri a noţiunii de structuraˇ, Academy of the People’s Republic of Romania. Bulletin of Sciences, section of Physical and Mathematical Sciences, 5, 41-48 (1953)
[5] Benado, M., Asupra teoriei divizibilitaˇţii, Academy of the People’s Republic of Romania. Bulletin of Sciences, section of Physical and Mathematical Sciences, 6, 263-270 (1954)
[6] Benado, M., Les ensembles partiellement ordonnés et le théorème de raffinement de Schreier. I, Czechoslovak Mathematical Journal, 4, 2, 105-129 (1954) · Zbl 0056.04602
[7] Bonchi, F.; Montanari, U., Coalgebraic models for reactive systems, Lecture Notes in Computer Science, 4703, 364-379 (2007) · Zbl 1151.68507
[8] Bonchi, F.; Montanari, U., G-reactive systems as coalgebras, Electronic Notes in Theoretical Computer Science, 203, 6, 3-17 (2008) · Zbl 1277.68163
[9] Cabrera, I.; Cordero, P.; Gutiérrez, G.; Martínez, J.; Ojeda-Aciego, M., Fuzzy congruence relations on nd-groupoids, International Journal on Computer Mathematics, 86, 1684-1695 (2009) · Zbl 1177.20078
[11] Cabrera, I. P.; Cordero, P.; Gutiérrez, G.; Martínez, J.; Ojeda-Aciego, M., Congruence relations on some hyperstructures, Annals of Mathematics and Artificial Intelligence, 56, 3-4, 361-370 (2009) · Zbl 1192.08001
[12] Chajda, I.; Kolařík, M., Nearlattices, Discrete Mathematics, 308, 21, 4906-4913 (2008) · Zbl 1151.06004
[13] Cordero, P.; Gutiérrez, G.; Martínez, J.; de Guzmán, I. P., A new algebraic tool for automatic theorem provers. Multisemilattice: a structure to improve the efficiency of provers in temporal logics, Annals of Mathematics and Artificial Intelligence, 42, 4, 369-398 (2004) · Zbl 1095.68110
[15] Cordero, P.; Mora, A.; de Guzmán, I. P.; Enciso, M., Non-deterministic ideal operators. An adequate tool for formalization in Data Bases, Discrete Applied Mathematics, 156, 6, 911-923 (2008) · Zbl 1142.68023
[16] Corsini, P.; Leoreanu, V., Applications of Hyperstructure Theory (2003), Kluwer · Zbl 1027.20051
[17] Damásio, C.; Medina, J.; Ojeda-Aciego, M., Termination of logic programs with imperfect information: applications and query procedure, Journal of Applied Logic, 5, 3, 435-458 (2007) · Zbl 1122.68025
[18] Ghilardi, S., Unification in intuitionistic logic, The Journal of Symbolic Logic, 64, 2, 859-880 (1999) · Zbl 0930.03009
[19] Hadzic, M.; Chang, E., Using coalgebra and coinduction to define ontology-based multi-agent systems, International Journal of Metadata, Semantics and Ontologies, 3, 3, 197-209 (2008)
[20] Hansen, D. J., An axiomatic characterization of multilattices, Discrete Mathematics, 33, 1, 99-101 (1981) · Zbl 0447.06005
[21] Hausmann, D.; Mossakowski, T.; Schröder, L., A coalgebraic approach to the semantics of the ambient calculus, Theoretical Computer Science, 366, 1-2, 121-143 (2006) · Zbl 1154.68088
[22] Jacobs, B., Many-sorted coalgebraic modal logic: a model-theoretic study, Theoretical Informatics and Applications, 35, 1, 31-59 (2001) · Zbl 0984.03019
[23] Jacobs, B., Coalgebraic trace semantics for combined possibilitistic and probabilistic systems, Electronic Notes in Theoretical Computer Science, 203, 5, 131-152 (2008) · Zbl 1279.68232
[25] Johnston, I. J., Some results involving multilattice ideals and distributivity, Discrete Mathematics, 83, 1, 27-35 (1990) · Zbl 0716.06004
[26] Khan, J.; Haque, A., Computing with data non-determinism: wait time management for peer-to-peer systems, Computer Communications, 31, 3, 629-642 (2008)
[27] Kim, J., Coinductive properties of causal maps, Lecture Notes in Computer Science, 5140, 253-267 (2008) · Zbl 1170.68499
[29] Konstantinidou, M.; Mittas, J., An introduction to the theory of hyperlattices, Math. Balkanica, 7, 187-193 (1977) · Zbl 0486.06004
[30] Martínez, J.; Gutiérrez, G.; de Guzmán, I. P.; Cordero, P., Generalizations of lattices via non-deterministic operators, Discrete Mathematics, 295, 1-3, 107-141 (2005) · Zbl 1085.06005
[33] Medina, J.; Ojeda-Aciego, M.; Ruiz-Calviño, J., Fuzzy logic programming via multilattices, Fuzzy Sets and Systems, 158, 6, 674-688 (2007) · Zbl 1111.68016
[34] Meng, S.; Barbosa, L., Components as coalgebras: the refinement dimension, Theoretical Computer Science, 351, 2, 276-294 (2006) · Zbl 1086.68031
[35] Mittas, J.; Konstantinidou, M., Sur une nouvelle généralisation de la notion de treillis: les supertreillis et certaines de leurs propriétés générales, Annales Scientifiques de l’Université de Clermont-Ferrand 2, Tome 94, Série Mathématiques, 25, 61-83 (1989) · Zbl 0722.06004
[37] Rudeanu, S.; Vaida, D., Multilattices in informatics: introductory examples, Revista de Logica, 4, 1-8 (2009)
[38] Rutten, J., Universal coalgebra: a theory of systems, Theoretical Computer Science, 249, 1, 3-80 (2000) · Zbl 0951.68038
[39] Schweigert, D., Near lattices, Mathematica Slovaca, 32, 3, 313-317 (1982) · Zbl 0492.06007
[40] Sun, M., Services and contracts: coalgebraically, Electronic Notes in Theoretical Computer Science, 212, 207-223 (2008) · Zbl 1286.68024
[41] Tomita, M., Efficient Parsing for Natural Language: A Fast Algorithm for Practical Systems (1985), Kluwer Academic Publishers
[42] Vaida, D., Note on some order properties related to processes semantics I, Fundamenta Informaticae, 73, 1-2, 307-319 (2006) · Zbl 1102.68078
[43] Varacca, D.; Winskel, G., Distributing probability over non-determinism, Mathematical Structures in Computer Science, 16, 1, 87-113 (2006) · Zbl 1093.18002
[44] Venema, Y., Automata and fixed point logic: a coalgebraic perspective, Information and Computation, 204, 4, 637-678 (2006) · Zbl 1110.68066
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.