Abstract
We here study some problems concerned with the computational analysis of finite partially ordered sets. We begin (in § 1) by showing that the matrix representation of a binary relationR may always be taken in triangular form ifR is a partial ordering. We consider (in § 2) the chain structure in partially ordered sets, answer the combinatorial question of how many maximal chains might exist in a partially ordered set withn elements, and we give an algorithm for enumerating all maximal chains. We give (in § 3) algorithms which decide whether a partially ordered set is a (lower or upper) semi-lattice, and whether a lattice has distributive, modular, and Boolean properties. Finally (in § 4) we give Algol realizations of the various algorithms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G. Birkhoff,Lattice Theory, Amer. Math. Soc. Colloq. Publ. XXV, rev. ed. 1961.
E. Szpilrajn,Sur l'extension de l'ordre partiel, Fund. Math. 16 (1930), 386–389.
R. M. Baer,Certain homomorphisms onto chains, Arch. Math. 8 (1957), 93–95.
A Proposal for Input-Output conventions in ALGOL 60, Comm. ACM, 7 (1964), 273–283.
Control Data Corp., 3000/6000 Algol Generic Reference Manual, Dec. 1967, Pub. No. 60214900.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Baer, R.M., Østerby, O. Algorithms over partially ordered sets. BIT 9, 97–118 (1969). https://doi.org/10.1007/BF01933247
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01933247