Algorithmic Counting of Zero-Dimensional Finite Topological Spaces With Respect to the Covering Dimension

Taking the covering dimension dim as notion for the dimension of a topological space, we first specify thenumber zdim_{T_0}(n) of zero-dimensional T_0-spaces on {1,...,n}$ and the number zdim(n) of zero-dimensional arbitrary topological spaces on {1,\ldots,n} by means oftwo mappings po and P that yieldthe number po(n) of partial orders on {1,...,n} and the set P(n) of partitions of {1,...,n}, respectively. Algorithms for both mappings exist. Assuming one for po to be at hand, we use our specification of zdim_{T_0}(n) and modify one for P in such a way that it computes zdim_{T_0}(n) instead of P(n). The specification of zdim(n) then allows to compute this number from zdim_{T_0}(1) to zdim_{T_0}(n) and the Stirling numbers of the second kind S(n,1) to S(n,n). The resulting algorithms have been implemented in C and we also present results of practical experiments with them. To considerably reduce the running times for computing zdim_{T_0}(n), we also describe a backtracking approach and its parallel implementation in C using the OpenMP library.

No reviews yet.

No comments yet.