HDA (Higher Dimensional Automaton)

HDA (higher dimensional automaton) はV. Pratt により[Pra91] で導入された概念らしい。

複数のプロセスが並列に動くとき, その状況を progress graph として \(\R ^n\) の部分集合で表すことができるが, データのロックと解放という区切りで, その領域を立方体の和集合として表すことができる。 そこで, degeneracy のない cubical set をそのモデルとして用いるというアイデアが出てきたが, それを並列処理を扱うためにより適した形にしたのが, HDA である。

Goubault の thesis では, degeneracy のない cubical set を semi-regular HDA, 加群の圏での degeneracy のない cubical object を general HDA と呼んでいる。

HDA に対するホモロジーは, Goubault の thesis で定義された。その後 Gaucher が Goubault の定義したホモロジーの改良を行 ない, globular homology というものを導入している。Gaucher は [Gau] という解説も書いている。

• globular CW-complex [GG03]
• (globular CW-complexの) S-homotopy
• (globular CW-complexの) T-homotopy
• globular homology

Kahl [Kah] によると, HDAのように並列処理の理論のために precubical set を使う際には, その geometric realization は Grandis の本 [Gra09] にある d-space として扱うべきのようである。d-space とは, その上の道として特定のものだけを許した空間である。

References

[Gau]

Philippe Gaucher. T-homotopy and refinement of observation (I) : Introduction. arXiv: math/0505152.

[GG03]

Philippe Gaucher and Eric Goubault. “Topological deformation of higher dimensional automata”. In: Homology Homotopy Appl. 5.2 (2003). Algebraic topological methods in computer science (Stanford, CA, 2001), pp. 39–82. arXiv: math/0107060. url: http://projecteuclid.org/euclid.hha/1088453321.

[Gra09]

Marco Grandis. Directed algebraic topology. Vol. 13. New Mathematical Monographs. Models of non-reversible worlds. Cambridge: Cambridge University Press, 2009, pp. x+434. isbn: 978-0-521-76036-2. url: http://dx.doi.org/10.1017/CBO9780511657474.

[Kah]

Thomas Kahl. Some collapsing operations for 2-dimensional precubical sets. arXiv: 1005.5443.

[Pra91]

Vaughn Pratt. “Modeling concurrency with geometry”. In: Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. POPL ’91. Orlando, Florida, USA: ACM, 1991, pp. 311–322. isbn: 0-89791-419-8. url: http://doi.acm.org/10.1145/99583.99625.