Abstract
The motivation for this paper comes from the following sources. First, one can observe that the two major concepts underlying the methods of reasoning with incomplete information are the concept of degree of truth of a piece of information and the concept of approximation of a set of information items. We shall refer to the theories employing the concept of degree of truth as to theories of fuzziness and to the theories employing the concept of approximation as to theories of roughness (see [6] for a survey). The algebraic structures relevant to these theories are residuated lattices ([7], [12], [13], [16], [17], [18], [22], [23]) and Boolean algebras with operators ([19], [21], [10], [11]), respectively. Residuated lattices provide an arithmetic of degrees of truth and Boolean algebras equipped with the appropriate operators provide a method of reasoning with approximately determined information. Both classes of algebras have a lattice structure as a basis. Second, both theories of fuzziness and theories of roughness develop generalizations of relation algebras to algebras of fuzzy relations [20] and algebras of rough relations ([4], [5], [9]), respectively. In both classes a lattice structure is a basis. Third, not necessarily distributive lattices with modal operators, which can be viewed as most elementary approximation operators, are recently developed in [24] (distributive lattices with operators are considered in [14] and [25]). With this background, our aim is to begin a systematic study of the classes of algebras that have the structure of a (not necessarily distributive) lattice and, moreover, in each class there are some operators added to the lattice which are relevant for binary relations. Our main interest is in developing relational representation theorems for the classes of lattices with operators under consideration. More precisely, we wish to guarantee that each algebra of our classes is isomorphic to an algebra of binary relations on a set. We prove the theorems of that form by suitably extending the Urquhart representation theorem for lattices ([26]) and the representation theorems presented in [1]. The classes defined in the paper are the parts which put together lead to what might be called lattice-based relation algebras. Our view is that these algebras would be the weakest structures relevant for binary relations. All the other algebras of binary relations considered in the literature would then be their signature and/or axiomatic extensions.
Throughout the paper we use the same symbol for denoting an algebra or a relational system and their universes.
The work was carried out in the framework of COST Action 274/TARSKI on Theory and Applications of Relational Structures as Knowledge Instruments.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Allwein, G., Dunn, J.M.: Kripke models for linear logic. J. Symb. Logic 58, 514–545 (1993)
Allwein, G.: Private communication (2003)
Chin, L., Tarski, A.: Distributive and modular laws in the arithmetic of relation algebras. University of California Publications in Mathematics 1, 341–384 (1951)
Comer, S.: An algebraic approach to the approximation of information. Fundamenta Informaticae 14, 492–502 (1991)
Comer, S.: On connections between information systems, rough sets and algebraic logic. In: Rasiowa, H., Rauszer, C. (eds.) Algebraic Methods in Logic, Algebra and Computer Science, Banach Center Publications, Warsaw (1993)
Demri, S., Orłowska, E.: Incomplete Iformation: Structure, Inference, Complexity. EATCS Monographs in Theoretical Computer Science. Springer, Heidelberg (2002)
Dilworth, R.P., Ward, N.: Residuated lattices. Transactions of the American Mathematical Society 45, 335–354 (1939)
Dunn, J.M.: Gaggle theory: an abstraction of Galois connections and residuation, with application to nagation, implication and various logical operators. In: van Eijck, J. (ed.) JELIA 1990. LNCS (LNAI), vol. 478, pp. 31–51. Springer, Heidelberg (2001)
Düntsch, I.: Rough relation algebras. Fundamenta Informaticae 21, 321–331 (1994)
Düntsch, I., Orłowska, E.: Beyond modalities: sufficiency and mixed algebras. In: Orłwska, E., Szałas, A. (eds.) Relational Methods for Computer Science Applications, pp. 263–285. Physica–Verlag, Heidelberg (2001)
Düntsch, I., Orłowska, E.: Boolean algebras arising from information systems. In: Proceedings of the Tarski Centenary Conference, Banach Centre, Warsaw, June 2001 (2002) (to appear)
Esteva, F., Godo, L.: Monoidal t–norm based logic: towards a logic for left–continuous t–norms. Fuzzy Sets and Systems 124, 271–288 (2001)
Esteva, F., Godo, L.: On complete residuated many-valued logics with t-norm conjunction. In: Proceedings of the 31st International Symposium on Multiple- Valued Logic, Warsaw, Poland, pp. 81–86 (2001)
Gehrke, M., Jónsson, B.: Bounded distributive lattices with operators. Mathematica Japonica 40(2), 207–215 (1994)
Grätzer, G.: General Lattice Theory. Birkhäuser, Basel (1978)
Hajek, P.: Metamathematics of Fuzzy Logic. Kluwer, Dordrecht (1998)
Höhle, U.: Commutative, residuated l-monoids. In: [18], pp. 53–106 (1996)
Höhle, U., Klement, U.P. (eds.): Non–Classical Logics and their Applications to Fuzzy Subsets. Kluwer, Dordrecht (1996)
Jónsson, B., Tarski, A.: Boolean algebras with operators. Part I. American Journal of Mathematics 73, 891–936 (1951)
Kawahara, Y., Furusawa, H.: An algebraic formalization of fuzzy relations. Fuzzy Sets and Systems 101, 125–135 (1999)
Orłowska, E.: Information algebras. In: Alagar, V.S., Nivat, M. (eds.) AMAST 1995. LNCS, vol. 936, pp. 50–65. Springer, Heidelberg (1995)
Orłowska, E., Radzikowska, A.M.: Information relations and opeators based on double residuated lattices. In: Procedings of the 6th International Workshop on Relational Methods in Computer Science RelMiCS 2001, Oisterwijk, Netherlands, pp. 185–199 (2001)
Orłowska, E., Radzikowska, A.M.: Double residuated lattices and their applications. In: de Swart, H. (ed.) RelMiCS 2001. LNCS, vol. 2561, pp. 171–189. Springer, Heidelberg (2002)
Orłowska, E., Vakarelov, D.: Lattices with modal operators and lattice–based modal logic. In: Proceedings of the 12th International Congress of Logic, Methodology and Philosophy of Science, Oviedo (August 2003) (to appear), Abstract in the Volume of Abstracts, 22–23
Sofronie-Stokkermans, V.: Duality and canonical extensions of bounded distributive lattices with operators, and applications to the semantics of non-classical logics. Studia Logica, Part I 64, 93–122, Part II, 151–172 (2000)
Urquhart, A.: A topological representation theorem for lattices. Algebra Universalis 8, 45–58 (1978)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Düntsch, I., Orłowska, E., Radzikowska, A.M. (2003). Lattice–Based Relation Algebras and Their Representability. In: de Swart, H., Orłowska, E., Schmidt, G., Roubens, M. (eds) Theory and Applications of Relational Structures as Knowledge Instruments. Lecture Notes in Computer Science, vol 2929. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24615-2_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-24615-2_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20780-1
Online ISBN: 978-3-540-24615-2
eBook Packages: Springer Book Archive