Efficient Computation of the Large Inductive Dimension Using Order- and Graph-theoretic Means

• Autorzy: Berghammer Rudolf , Schnoor Henning , Winter Michael

Identyfikatory

DOI

10.3233/FI-2020-1981

• Języki publikacji: EN

Abstrakty

EN

Finite topological spaces and their dimensions have many applications in computer science, e.g., in digital topology, computer graphics and the analysis and synthesis of digital images. Georgiou et. al. [11] provided a polynomial algorithm for computing the covering dimension dim (X, 𝒯 ) of a finite topological space (X, 𝒯 ). In addition, they asked whether algorithms of the same complexity for computing the small inductive dimension ind (X, 𝒯 ) and the large inductive dimension Ind (X, 𝒯 ) can be developed. The first problem was solved in a previous paper [4]. Using results of the that paper, we also solve the second problem in this paper. We present a polynomial algorithm for Ind (X, 𝒯 ), so that there are now efficient algorithms for the three most important notions of a dimension in topology. Our solution reduces the computation of Ind (X, 𝒯 ), where the specialisation pre-order of (X, 𝒯 ) is taken as input, to the computation of the maximal height of a specific class of directed binary trees within the partially ordered set. For the latter an efficient algorithm is presented that is based on order- and graph-theoretic ideas. Also refinements and variants of the algorithm are discussed.

Słowa kluczowe

EN

partially ordered sets; algorithms; topological spaces; scientific computing; computer graphics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 177, nr 2
• Strony: 95--113
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Berghammer Rudolf

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

autor

Schnoor Henning

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

autor

Winter Michael

• Department of Computer Science, Brock University, St. Catharines, ON, Canada

Bibliografia

• [1] Alexandroff P. Diskrete Räume. Matematicheskij Sbornik NS 1937. 2:501-518. URL http://mi.mathnet.ru/eng/msb/v44/i3/p501.
• [2] Arenas FG. Alexandroff spaces. Acta Mathematica Universitatis Comenianae 68, pp. 17-25 (1999).
• [3] Berghammer R, Neumann F. RELVIEW - An OBDD-based Computer Algebra system for relations. In: V.G. Gansha, E.W. Mayr, E. Vorozhtsov (eds.): Computer Algebra in Scientific Computing. Lecture Notes in Computer Science, vol. 3718, Spriger 2005 pp. 40-51. doi:10.1007/11555964_4.
• [4] Berghammer R, Winter M. Order- and graph-theoretic investigation of dimensions of finite topological spaces. Monatshefte für Mathematik 2019. 190:33-78. doi:10.1007/s00605-019-01261-1.
• [5] Coornaert M. Topological dimension and dynamical systems. Springer (2015). ISBN-978-3-319-19793-7, 0172-5939.
• [6] Davey BA, Priestley HA. Introduction to lattices and order. Cambridge University Press 2002. ISBN-13:978-0521784511, 10:0521784514.
• [7] Diestel R. Graph theory. Springer (2005).
• [8] Engelking R. Dimension theory. North-Holland Mathematical Library, vol. 19, North-Holland 1978.
• [9] Georgiou DN, Megaritis AC. Covering dimension and finite spaces. Applied Mathematics and Computation 2011. 218(7):3122-3130. doi.org/10.1016/j.amc.2011.08.040.
• [10] Georgiou DN, Megaritis AC, Moshokoa SP. Small inductive dimension and Alexandroff topological spaces. Topology and its Applications 2014. 168:103-119. doi:10.1016/j.topol.2014.02.014.
• [11] Georgiou DN, Megaritis AC. An algorithm of polynomial order for computing the covering dimension of a finite space. Applied Mathematics and Computation 2014. 231:276-283. doi:10.1016/j.amc.2013.12.185.
• [12] Georgiou DN, Megaritis AC, Moshokoa SP. A computing procedure for the small inductive dimension of a finite T0-space. Computational and Applied Mathematics 2015. 34(1):401-415. doi:10.1007/s40314-014-0125-z.
• [13] Georgion DN, Megaritis AC, Moshokoa SP. Finite spaces: a reduction algorithm for the computation of the small inductive dimension. of a finite T0-space. Computational and Applied Mathematics 2017. 36:791-803. doi:10.1007/s40314-015-0261-0.
• [14] Kahn AB. Topological sorting of large networks. Communications of the ACM 1962. 5(11):558-562. doi:10.1145/368996.369025.
• [15] Kelley JL. General topology, Springer (1975). ISBN-978-0-387-90125-1, 0072-5285.
• [16] Sharir M. A strongly connectivity algorithm and its applications to data flow analysis. Computers and Mathematics with Applications 1981. 7(1):67-72. doi:10.1016/0898-1221(81)90008-0.
• [17] Stong RE. Finite topological spaces. Transactions of the American Mathematical Society 1966. 123:325-340. S0002-9947-1966-0195042-2.pdf.
• [18] Tarjan RE. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1972. 1(2):146-160. doi:10.1137/0201010.
• [19] Wiederhold P, Wilson RG. Dimension for Alexandrov spaces. In: R.A. Melter, A.Y. Wu (eds.): Vision geometry. Proceedings of Society Phot-Optical Instrumentation Engineers, vol. 1832, 1992 pp. 13-22.
• [20] RELVIEW-homepage: http://www.informatik.uni-kiel.de/~progsys/relview/.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).