トポロジーの計算機科学への応用

21世紀になって, (代数的)トポロジーの様々な分野への応用が発見されてきたようで, 面白い。

計算機科学の理論的な面では, 並列処理の理論への応用がある。 モデル圏の構造が発見されているので, ホモトピー論 (代数的トポロジー) の研究対象と考えてよいだろう。実際, 並列処理の理論などに現れる構造を一般化したものを研究する分野として directed algebraic topology という名前を提唱している人もいる。Survey として, Grandis の [Gra07] がある。それによると, 並列処理の理論以外に, rewriting system や 非可換幾何学biological system のモデルなどとも関係があるらしい。 Husainov の [Hus04] では, small category の homology が用いられている。

Mrozek の [Mro17] で知ったのであるが, finite space を画像の解析に使うというアイデアもある。Mrozek は Kovalevsky の [Kov89] を挙げている。

計算機科学とは言えないかもしれないが, 構文解析に関係あるもので word がある。Turaevが結び目を研究するための概念を word を調べるために導入している。

新しい話題としては, quantum computing がある。 圏と関手の言葉を用いて, 色々新しい試みが行なわれている。Freedman らは topological modular functor との関係を調べている。

あの Voevodsky が “homotopy \(\lambda \)-calculus” という概念を考えているのを知ったときは驚いたが, それがその後の homotopy type theory に発展したのだろう。この homotopy \(\lambda \)-calculus の論文は Baez の web site から download できる。

最近では, いわゆる topological data analysis という分野が急速に発展しているように思える。膨大なデータ (point cloud) を persistent homology などの topological な道具で調べる分野である。

計算の複雑性の理論を small category や functor に導入しようという試みも ある。Basu と Isik の [BI20] である。

Computer science と言えるのかどうか分からないが, digital image をトポロジーの視点から調べる digital topology という分野もあるようである。

  • digital topology

Staecker [Sta] によると, 抽象的な digital image の定義に基づいた digital topology は Rosenfeld の仕事 [Ros86] に起源があるようである。

画像に関係した分野としては, mathematical morphology というものもある。 Matheron と Serra により1964年に創始されたようである。 彼等によるスライドでその起源が説明されている。 その Serra による Introduction [Ser86] がある。 最近のものでは, Najman と Talbot の本 [NT13] がある。

  • mathematical morphology

Grayscale の画像は, 格子上の関数と考えられるが, Boutry と Bertrand と Najman の [BBN] では, discrete Morse theory との関係が調べられている。

他には以下のような話題がある。

References

[BBN]

Nicolas Boutry, Gilles Bertrand, and Laurent Najman. Gradient Vector Fields of Discrete Morse Functions and Watershed-cuts. arXiv: 2203.11512.

[BI20]

Saugata Basu and Umut Isik. “Categorical complexity”. In: Forum Math. Sigma 8 (2020), Paper No. e34, 63. arXiv: 1610.07737. url: https://doi.org/10.1017/fms.2020.26.

[Gra07]

Marco Grandis. “Directed algebraic topology, categories and higher categories”. In: Appl. Categ. Structures 15.4 (2007), pp. 341–353. url: http://dx.doi.org/10.1007/s10485-007-9084-5.

[Hus04]

Ahmet A. Husainov. “On the homology of small categories and asynchronous transition systems”. In: Homology Homotopy Appl. 6.1 (2004), pp. 439–471. url: http://projecteuclid.org/euclid.hha/1139839561.

[Kov89]

V.A Kovalevsky. “Finite topology as applied to image analysis”. In: Computer Vision, Graphics, and Image Processing 46.2 (1989), pp. 141–161. url: http://www.sciencedirect.com/science/article/pii/0734189X89901655.

[Mro17]

Marian Mrozek. “Conley-Morse-Forman theory for combinatorial multivector fields on Lefschetz complexes”. In: Found. Comput. Math. 17.6 (2017), pp. 1585–1633. arXiv: 1506 . 00018. url: https://doi.org/10.1007/s10208-016-9330-z.

[NT13]

Laurent Najman and Hugues Talbot. Mathematical morphology. Wiley, 2013. url: http://cds.cern.ch/record/2104784.

[Ros86]

Azriel Rosenfeld. ““Continuous” functions on digital pictures”. In: Pattern Recognition Letters 4.3 (1986), pp. 177–184.

[Ser86]

J. Serra. “Introduction to Mathematical Morphology”. In: Computer Vision, Graphics and Image Processing 35 (1986), pp. 283–305.

[Sta]

P. Christopher Staecker. Digital homotopy relations and digital homology theories. arXiv: 2106.01171.