Decomposition of Relations and Concept Lattices

• Autorzy: Berghammer R. , Winter M.
• Języki publikacji: EN

Abstrakty

EN

We introduce the decomposition of an arbitrary relation into a sequential composition of three relations, viz. of a mapping with a partial order and then the transpose of a mapping. After presenting some basic properties, we investigate the specific classes of junkfree, irreducible and minimal decompositions and show that for all relations a minimal decomposition exists. We also study decompositions with regard to DedekindMacNeille completions and concept lattices. These constructions are closely related to decompositions of relations. In our setting the fundamental theorem of concept lattices states that concept lattices are minimal-complete decompositions and all such decompositions are isomorphic. As a further main result we prove that the cutDedekindMacNeille completion of the order that belongs to the minimal decomposition of a relation is isomorphic to the concept lattice of that relation. Instead of considering binary relations on sets, we will work point-free within the general framework of allegories. This complement-free approach implies that the results of the paper can be applied to all models of these algebraic structures, including, for instance, lattice-valued fuzzy relations.

Słowa kluczowe

EN

division allegory; power allegory; relation algebra; partial order; complete lattice; decomposition; concept lattice; cut completion

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 126, nr 1
• Strony: 37--82
• Opis fizyczny: Bibliogr. 37 poz.

Twórcy

autor

Berghammer R.

• Institut für Informatik, Christian-Albrechts-Universität zu Kiel, 24098 Kiel, Germany

autor

Winter M.

• Department of Computer Science, Brock University, St. Catharines, Ontario, Canada, L2S 3A1

Bibliografia

• [1]. Barbut M., Monjardet B.: Ordre et Classification: Algebre et Combinatoire. Hachette (1970).
• [2]. BehnkeR., Berghammer R., Meyer E., Schneider R: RELVIEW-A system for calculation with relations and relational programming. In: Astesiano E. (ed.): Fundamental Approaches to Software Engineering. Lecture Notes in Computer Science, Vol. 1382, Springer, 318-321 (1998).
• [3]. Belohlavek R.: Lattices generated by binary fuzzy relations (extended abstract). In: Abstracts of the Fourth International Conference on Fuzzy Sets Theory and Its Applications. Liptovsky Jan, Slovakia, p.11 (1999).
• [4]. Belohlavek R.: Reduction and a simple proof of characterization of fuzzy concept lattices. Fundamenta Informaticae 46(4), 277-285 (2001).
• [5]. Belohlavek R.: Fuzzy Relational Systems: Foundations and Principles. Kluwer Academic/Plenum Publishers, New York (2002).
• [6]. Belohlavek R.: Concept lattices and order in fuzzy logic. Annals of Pure and Applied Logic 128, 277-298 (2004).
• [7]. Berghammer R., Schmidt G., Zierer H.: Symmetric quotients and domain constructions. Information Processing Letters 33, 163-168 (1989/90).
• [8]. Berghammer R., Leoniuk B., Milanese U.: Implementation of relational algebra using binary decision diagrams, In: de Swart H. (ed.): Relational Methods in Computer Science. Lecture Notes in Computer Science, Vol. 2561, Springer, 241-257 (2002).
• [9]. Berghammer R., Neumann F.: RELVIEW- An OBDD-based computer algebra system for relations. In: Gansha V.G., Mayr E.W., Vorozhtsov E. (eds.): Computer Algebra in Scientific Computing, Lecture Notes in Computer Science, Vol. 3718, Springer, 40-51 (2005).
• [10]. Berghammer R., Schmidt G.: Algebraic visualization of relations using RELVIEW. In: Gansha V.G., Mayr E.W., Vorozhtsov E. (eds.): Computer Algebra in Scientific Computing, Lecture Notes in Computer Science, Vol. 4770, Springer, 58-72 (2007).
• [11]. Berghammer R., Braßel B.: Computing and visualizing closure objects using relations and RELVIEW. In: Gerdt V.P., Mayr E.W., Vorozhtsov E.V (eds.): Computer Algebra in Scientific Computing. Lecture Notes in Computer Science, Vol. 5743, Springer, 29-44 (2009).
• [12]. Berghammer R., Winter M.: Embedding mappings and splittings with applications. Acta Informatica 47, 77-110(2010).
• [13]. Birkhoff G.: Lattice Theory. American Mathematical Society Colloquium Publications Vol. XXV, 3rd edition (1968).
• [14]. Davey B.A., Priestley H.A.: Introduction to Lattices and Order. Cambridge University Press, 3rd printing (2006).
• [15]. Dedekind R.: Stetigkeit und irrationale Zahlen. Friedrich Vieweg & Sohn (1912).
• [16]. Durakova D., Krajci S., Snasel V, Vojtas P: Conceptual structures. Arbeitstagung Allgemeine Algebra, 2002.
• [17]. Freyd P.J., Scedrov A.: Categories, Allegories. North-Holland (1989).
• [18]. Furusawa H., Kahl W.: A study on symmetric quotiens. University of the Federal Armed Forces Munich, Report 1998-06 (1998).
• [19]. Gansner E.R., Koutsofios E., North S.C., Vo K.P.: A technique for drawing directed graphs, IEEE Transactions on Software Engineering 19, 214-230 (1993).
• [20]. Ganter B.: Two basic algorithms in concept analysis. FB 4 Preprint No. 831, Technische Hochschule Darmstadt (1984).
• [21]. GanterB., Wille R.: Formal Concept Analysis: Mathematical Foundations. Springer (1999).
• [22]. Ganter B., Stumme G., Wille R.: Formal Concept Analysis: Foundations and applications. Lecture Notes in Artificial Intelligence, Vol. 3626, Springer (2005).
• [23]. Gehrke, M.: Generalized Kripke frames. Studia Logica 84(2), 241-275 (2006).
• [24]. Jaoua A., Belkhiter N., Ounalli H., Moukam T.: Databases. in: Brink C., Kahl W., Schmidt G. (eds.): Relational Methods in Computer Science, Advances in Computing Science, Springer (1997).
• [25]. MacNeille H.M.: Partially ordered sets. Transactions of the American Mathematical Society 42, 416-460 (1937).
• [26]. Maddux R.D.: Relation Algebras. Elsevier (2006).
• [27]. Nourine J., Raynaud O.: A fast algorithm for building lattices. Information Processing Letters 71, 199-204 (1999).
• [28]. Schmidt G., Strohlein T.: Relations and Graphs. Discrete Mathematics for Computer Scientists. EATCS Monographs on Theoretical Computer Science, Springer (1993).
• [29]. Schmidt G.: Rectangles, fringes, and inverses. In: Berghammer R., Möller B., Struth G. (eds.): Relations and Kleene algebra in Computer Science. Lecture Notes in Computer Science, Vol. 4988, Springer, 352-366 (2008).
• [30]. Schmidt G.: Relational Mathematics. Encyclopedia of Mathematics and its Applications, vol. 132, Cambridge University Press (2011).
• [31]. Tarski A.: On the calculus of relations. Journal of Symbolic Logic 6, 73-89 (1941).
• [32]. Tarski A., Givant S.: A Formalization of Set Theory Without Variables. American Mathematical Society Colloquium Publications Vol. 41 (1987).
• [33]. Wille, R.: Restructering Lattice Theory. In: Rival, I. (eds.): Ordered Sets. Reidel, 445-470 (1982).
• [34]. Winter M.: Structural theory of heterogeneous relation algebras with applications in nondeterminism in programming languages (in German). Dissertation, Universitat der Bundeswehr München, (1998).
• [35]. Winter M.: Decomposing relations into orderings. In: Berghammer R., Möller B., Struth G. (eds.): Relational and Kleene-algebraic Methods in Computer Science. Lecture Notes in Computer Science, Vol. 3051, Springer, 265-277 (2004).
• [36]. Winter M.: Goguen Categories - A Categorical Approach to L-fuzzy Relations. Trends in Logic 23, Springer (2007).
• [37]. Zierer H.: Programming with function objects, constructive generation of semantic domains application to partial evaluation (in German). Dissertation, Technische Universität München (1988).