Abstract
Relation algebra is well suited for dealing with many problems on ordered sets. Introducing lattices via order relations, this suggests to apply it and tools for its mechanization for lattice-theoretical problems, too. We combine relation algebra and the BDD-based specific purpose Computer Algebra system RelView to solve some algorithmic problems on orders and lattices and to visualize their solutions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Behnke, R., Berghammer, R., Meyer, E., Schneider, P.: RelView—a system for calculation with relations and relational programming. In: Astesiano, E. (ed.) Proceedings of 1st Conference on Fundamental Approaches to Software Engineering, pp. 318–321. LNCS, vol. 1382. Springer, Heidelberg (1998)
Berghammer R. and Schmidt G. (1983). Discrete ordering relations. Discr. Math. 43: 1–7
Berghammer R. (1999). Combining relational calculus and the Dijkstra-Gries method for deriving relational programs. Inf. Sci. 119: 155–171
Berghammer R. and Hoffmann T. (2000). Deriving relational programs for computing kernels by reconstructing a proof of Richardson’s theorem. Sci. Comput. Prog. 38: 1–25
Berghammer R. and Hoffmann T. (2001). Relational depth-first-search with applications. Inf. Sci. 139: 167–186
Berghammer, R., Leoniuk, B., Milanese, U.: Implementation of relation algebra using binary decision diagrams. In: de Swart, H. (ed.): Proceedings of 6th International Workshop Relational Methods in Computer Science, pp. 241–257. LNCS, vol. 2561. Springer, Heidelberg (2002)
Berghammer R. (2004). Computation of cut completions and concept lattices using relational algebra and RelView. J. Relat. Meth. Comput. Sci. 1: 50–72
Berghammer, R., Neumann, F.: RelView—An OBDD-based Computer Algebra system for relations. In: Gansha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) Proceedings of 8th International Workshop Computer Algebra in Scientific Computing, pp. 40–51. LNCS, vol. 3718. Springer, Heidelberg (2005)
Berghammer R. and Fronk A. (2006). Exact computation of minimum feedback vertex sets with relational algebra. Fund. Inform. 70: 301–316
Berghammer, R., Milanese, U.: Relational approach to Boolean logic problems. In: MacCaull, W., Dünsch, I., Winter, M. (eds.) Proceedings of 8th International Workshop Relational Methods in Computer Science, pp. 48–59. LNCS, vol. 3929. Springer, Heidelberg (2006)
Berghammer, R., Schmidt, G.: Algebraic visualization of relations using RelView. In: Gansha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds.) Proceedings of 10th International Workshop Computer Algebra in Scientific Computing, pp. 58–72. LNCS, vol. 4770. Springer, Heidelberg (2007)
Birkhoff, G.: Lattice theory, 3rd edn. American Math. Society Coll. Publ., Vol. XXV, American Math. Society, Providence (1967)
Bonnet R. and Pouzet M. (1969). Extensions et stratifications d’ensembles disperses. C.R. Acad. Sci. 268(Serie A): 1512–1515
Davey B.A. and Priestley H.A. (1990). Introduction to Lattices and Order. Cambridge University Press, Cambridge
Dedekind R. (1900). Über die von drei Moduln erzeugte Dualgruppe. Math. Ann. 53: 371–403
Dijkstra E.W. and Scholten C.S. (1990). Predicate Calculus and Program Semantics. Springer, Heidelberg
Freese, R., Jezek, J., Nation, J.B.: Free lattices. Mathematical Surveys and Monographs, vol. 42. American Math. Society, Providence (1995)
Freese, R.: Automated lattice drawing. In: Eklund, P. (ed.) Proceedings of International Conference on Formal Concept Analysis, pp. 112–127. LNCS, vol. 2961. Springer, Heidelberg (2004)
Ganter B. and Wille R. (1999). Formal concept Analysis: Mathematical Foundations. Springer, Heidelberg
Gries D. (1981). The Science of Computer Programming. Springer, Heidelberg
Hermes, H.: Einführung in die Verbandstheorie. Grundlehren der math. Wissenschaften in Einzeldarstellungen, 2nd edn. Springer, Heidelberg (1967)
Hulpke, A.: Computing normal subgroups. In: Proc. Int. Symposium on Symbolic and Algebraic Computation, pp. 194–198. ACM Press, New York (1998)
Kahn A.B. (1962). Topological sorting of large networks. Commun. ACM 5: 558–562
Lamport L. (1978). Time, clocks and the ordering of events in a distributed system. Commun. ACM 21: 558–565
Lang S. (2002). Algebra. Graduate Texts in Mathematics, 3rd edn. Springer, Heidelberg
Leoniuk, B.: ROBDD-basierte Implementierung von Relationen und relationalen Operationen mit Anwendungen. Dissertation, Univ. Kiel (2001)
Maddux R. (2006). Relation algebras. Studies in Logic and the Fundations of Mathematics, vol. 150. Elsevier, Amsterdam
Milanese, U.: Zur Implementierung eines ROBDD-basierten Systems für die Manipulation und Visualisierung von Relationen. Dissertation, Univ. Kiel (2003)
Nemitz W.C. (1969). Semi-Boolean lattices. Notre Dame Journal of Formal Logic 16: 235–238
Nourine L. and Raynaud O. (1999). A fast algorithm for building lattices. Inform. Proc. Let. 70: 259–264
Ore O. (1938). Structures and group theory II. Duke Math. J. 4: 247–269
Pruesse G. and Ruskey F. (1994). Generating all linear extensions fast. SIAM J. Comput. 23: 373–386
Schmidt, G., Ströhlein, T.: Relations and graphs. Discrete Mathematics for Computer Scientists, EATCS Monographs on Theoret. Comput. Sci., Springer Verlag (1993)
Schmidt, R.: Subgroup lattices of groups. de Gruyter Expositions in Mathematics, vol. 14, de Gruyter (1994)
Skornjakow L.A. (1973). Elemente der Verbandstheorie. Akademie-Verlag, Berlin
Sperner E. (1928). Ein Satz über Untermengen einer endlichen Menge. Math. Zeitschrift 27: 544–548
Szpilrajn E. (1930). Sur l’extension de l’ordre partiel. Fundamenta Math. 16: 386–389
Tarski A. (1941). On the calculus of relations. J. Symbolic Logic 6: 73–89
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Berghammer, R. Applying relation algebra and RelView to solve problems on orders and lattices. Acta Informatica 45, 211–236 (2008). https://doi.org/10.1007/s00236-008-0072-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00236-008-0072-5