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

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

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

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

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

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

• word problem

関連したものとして, rewriting system の理論がある。Forest と Mimram の [FM] では, [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.

[FM]

Simon Forest and Samuel Mimram. Rewriting in Gray categories with applications to coherence. arXiv: 2109.05369.

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

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