Algorithms over partially ordered sets

Autor: R. M. Baer, O. Østerby
Rok vydání: 1969
Předmět:
Zdroj: Baer, R M & Østerby, O 1969, ' Algorithms over partially ordered sets ', BIT Numerical Mathematics, vol. 9, no. 2, pp. 97-118 . https://doi.org/10.1007/BF01933247
ISSN: 1572-9125
0006-3835
DOI: 10.1007/bf01933247
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: