Word Problem

Word とは alphabet の有限列のことである。 群を生成元と関係式で表わしたとき, 生成元を alphabet として, 群の元はその word で表わされる。問題は, 二つの word が同じかどうかをどうやって判定するかである。

この word problem に関連が深い群の class として, automatic group がある。 この automatic という言葉は, オートマトン (automaton) から来ている。

• automatic group
• biautomatic group

Holt の [Hol98] によると, Cannon の仕事 [Can84] に基づき, Thurston により1986年に導入されたようである。 文献としては, Epstein らの [Eps+92] を挙げるべきだろうか。 歴史的視点からの解説として Sarah Rees の [Ree] もある。

この MathOverflow の質問で知ったのであるが, Thurston は, 群を調べるのに UNIX の utility grep が使えることに気がつき, それが automatic group の理論に発展したようである。Notices of the A.M.S. の記事 [GS16] の Mosher の文にある。

Turaev [Tur07c; Tur08] は, 群とは限らない集合の元を alphabet とする word について, トポロジーからのアイデアにより調べることを提唱していて興味深い。Move や linking や polynomial invariant など, 結び目を研究するための概念を word に導入している。 Cobordism や surgery などの言葉も登場する。Turaev は word については [Tur07a] という研究もしている。

解説としては, Turaev 自身による [Tur07b] がある。

群以外の代数的構造に対しても, word problem は考えられている。 例えば, Delpeuch は [Del20] で double category の場合, Vicary との共著 [DV] で braided monoidal category について考えている。

References

[Can84]

James W. Cannon. “The combinatorial structure of cocompact discrete hyperbolic groups”. In: Geom. Dedicata 16.2 (1984), pp. 123–148. url: https://doi.org/10.1007/BF00146825.

[Del20]

Antonin Delpeuch. “The word problem for double categories”. In: Theory Appl. Categ. 35 (2020), Paper No. 1, 1–18. arXiv: 1907. 09927.

[DV]

Antonin Delpeuch and Jamie Vicary. The word problem for braided monoidal categories is unknot-hard. arXiv: 2105.04237.

[Eps+92]

David B. A. Epstein et al. Word processing in groups. Boston, MA: Jones and Bartlett Publishers, 1992, pp. xii+330. isbn: 0-86720-244-0.

[GS16]

“William P. Thurston, 1946–2012”. In: Notices Amer. Math. Soc. 63.1 (2016). Ed. by David Gabai and coordinating editors Steve Kerckhoff, pp. 31–41. url: https://doi.org/10.1090/noti1324.

[Hol98]

Derek F. Holt. “Automatic groups, subgroups and cosets”. In: The Epstein birthday schrift. Vol. 1. Geom. Topol. Monogr. Geom. Topol. Publ., Coventry, 1998, pp. 249–260. arXiv: math/9810190. url: https://doi.org/10.2140/gtm.1998.1.249.

[Ree]

Sarah Rees. The development of the theory of automatic groups. arXiv: 2205.14911.

[Tur07a]

Vladimir Turaev. “Coalgebras of words and phrases”. In: J. Algebra 314.1 (2007), pp. 303–323. arXiv: math/0408258. url: http://dx.doi.org/10.1016/j.jalgebra.2007.02.029.

[Tur07b]

Vladimir Turaev. “Lectures on topology of words”. In: Jpn. J. Math. 2.1 (2007), pp. 1–39. arXiv: math / 0609516. url: http://dx.doi.org/10.1007/s11537-007-0634-2.

[Tur07c]

Vladimir Turaev. “Topology of words”. In: Proc. Lond. Math. Soc. (3) 95.2 (2007), pp. 360–412. arXiv: math/0503683. url: http://dx.doi.org/10.1112/plms/pdm014.

[Tur08]

Vladimir Turaev. “Cobordisms of words”. In: Commun. Contemp. Math. 10.suppl. 1 (2008), pp. 927–972. arXiv: math/0511513. url: http://dx.doi.org/10.1142/S0219199708003101.