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

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

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

• 並列処理の理論
• directed algebraic topology

より古くは, algorithm の複雑性に代数的トポロジーの道具を用いた Smale の仕事 [Sma87] があることを, 最近知った。そこでは, 代数方程式の根を求める algorithm の複雑性を考えるために Schwarz genus が用いられている。 また topological complexity of algorithm という言葉が導入されている。 最近では, topological complexity というと, Farber により導入された不変量のことを意味することが多いが, その Farber の [Far03] の Introduction の最後には, Smale の仕事が挙げられているので topological complexity という名前は Smale の論文から取ったものだろう。

• topological complexity of algorithm

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

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

• word problem

関連したものとして, rewriting system の理論がある。Forest と Mimram の [FM22] では, [BN98] と [Ter03] が参照されている。 Forest と Mimram は Gray category での monoid や adjunction などの coherence を証明するのに使っている。

• rewriting system

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

• quantum computing

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

• homotopy type theory

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

• topological data analysis

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

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

• digital topology

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

• mathematical morphology

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

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

• 計算機科学のための圏論
• 数理論理学との関連
• entropy

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.

[BN98]

Franz Baader and Tobias Nipkow. Term rewriting and all that. Cambridge University Press, Cambridge, 1998, pp. xii+301. isbn: 0-521-45520-0; 0-521-77920-0. url: https://doi.org/10.1017/CBO9781139172752.

[Far03]

Michael Farber. “Topological complexity of motion planning”. In: Discrete Comput. Geom. 29.2 (2003), pp. 211–221. arXiv: math/0111197. url: http://dx.doi.org/10.1007/s00454-002-0760-9.

[FM22]

Simon Forest and Samuel Mimram. “Rewriting in Gray categories with applications to coherence”. In: Math. Structures Comput. Sci. 32.5 (2022), pp. 574–647. arXiv: 2109.05369. url: https://doi.org/10.1017/s0960129522000299.

[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.

[Ser86]

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

[Sma87]

Steve Smale. “On the topology of algorithms. I”. In: J. Complexity 3.2 (1987), pp. 81–89. url: http://dx.doi.org/10.1016/0885-064X(87)90021-5.

[Ter03]

Terese. Term rewriting systems. Vol. 55. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, 2003, pp. xxii+884. isbn: 0-521-39115-6.